Placing quantified variants of 3-SAT and Not-All-Equal 3-SAT in the polynomial hierarchy

Britta Dorn; Charles Semple; Janosch D\"ocker; Simone Linz

REVIEW 5 major objections 4 minor 17 references

Placing quantified variants of 3-SAT and Not-All-Equal 3-SAT in the polynomial hierarchy

T0 review · 5 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Quantified 3-SAT stays $\Pi_2^P$-complete under strict per-variable appearance limits, and quantified NAE-3-SAT stays complete in a linear monotone one-universal setting.

desk verdict Genuinely new threshold results for quantified bounded-appearance SAT, but the extracted text hides negation bars in key gadgets—verify the PDF before trusting the completeness proofs. read the letter →

arxiv 1908.05361 v2 pith:G3FZMO7F submitted 2019-08-14 cs.CC

Janosch Döcker , Britta Dorn , Simone Linz , Charles Semple This is my paper · ORCID

classification cs.CC MSC 68Q1768Q2503D15

keywords quantified3-SATNAE-3-SATboundedvariableappearancespolynomialhierarchyPi_2^P-completenessenforcergadgetsmonotonelinearformulas

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper draws a boundary for two quantified satisfiability problems inside the polynomial hierarchy. Its main results show that $\forall\exists$ 3-SAT remains $\Pi_2^P$-complete when every variable appears exactly twice unnegated and exactly twice negated and when the number of universal and existential variables is equal; the same remains true when universal variables appear only once in each polarity and existential variables twice in each polarity. For Not-All-Equal 3-SAT, the paper proves $\Pi_2^P$-completeness for linear monotone formulas in which each universal variable appears exactly once, each existential variable appears exactly three times, and no clause contains more than one universal variable. It also separates the easier territory: some one-literal universal variants are NP-complete, and certain NAE variants with existential variables appearing twice are in co-NP or polynomial time. The practical upshot is a near-complete map of where the quantified problems jump between the first and second levels of the hierarchy as variable appearances are restricted.

What carries the argument

The arguments run through polynomial-time reductions that are carried by small Boolean gadgets called enforcers. The basic S-enforcer $S(\ell_1,\ell_2,\ell_3)$ is a five-clause formula over three auxiliary variables that is satisfiable exactly when at least one of the three literals is true; from it the paper builds $x^{(2)}$ and $E(x)$, gadgets that force a designated variable to take the value true while respecting fixed appearance counts. Two quantified enforcers, $Q_1$ and $Q_3$, add blocks of universal variables in multiples that rebalance the universal and existential counts. The NAE half uses monotone gadgets: $NE_{\mathrm{aux}}$ forces two variables to differ, $EQ$ forces equality, $NE$ combines them, and $P_1$ pads the appearance count of an existential variable without changing satisfiability. In the reductions, these gadgets are combined with a variable-splitting step, in which each appearance of a variable is replaced by a fresh variable linked by equality chains, and a clause-complement step, in which each clause is conjoined with its negated version; together these steps force all copies of a variable to agree and exactly control how many times each polarity appears.

What would settle it

Set the universal variable $c_i$ to false and the existential copy $y_i$ to true in the Step 1 gadget of Theorem 3.2. Taken literally, both copies of $S_u(c_i,y_i,y_i)$ are satisfiable by Observation 2.1, so the enforcer does not force $y_i=c_i$; this failure, if confirmed in the full construction, is enough to invalidate the equivalence in statement 3.2.1.

Watch

Extended reading notes

Core claim

The central claim is that the quantified satisfiability problems $\forall\exists$ 3-SAT and $\forall\exists$ NAE-3-SAT keep their $\Pi_2^P$-completeness under appearance bounds that are essentially the strictest possible without descending in the polynomial hierarchy. Theorem 3.1 proves Balanced $\forall\exists$ 3-SAT-(2,2,2,2) is $\Pi_2^P$-complete: every variable, universal or existential, appears exactly twice unnegated and twice negated; every clause has exactly three distinct variables; and the universal and existential blocks have equal size. Theorem 3.2 strengthens this to Balanced $\forall\exists$ 3-SAT-(1,1,2,2), and Theorems 3.3 and 3.4 resolve the intermediate regimes, giving NP-completeness when each universal variable has exactly one appearance in total and $\Pi_2^P$-completeness when each universal variable has one unnegated and one negated appearance. On the NAE side, Theorem 4.1 shows Monotone $\forall\exists$ NAE-3-SAT-(1,3) is $\Pi_2^P$-complete even for linear formulas with at most one universal variable per clause, while the final section places Monotone $\forall\exists$ NAE-3-SAT-(s,2) in co-NP and its $(1,2)$ case in P. Quantified NAE-3-SAT can therefore tolerate a single universal appearance, a regime in which ordinary $\forall\exists$ 3-SAT is only NP-complete unless the polynomial hierarchy collapses.

Load-bearing premise

The load-bearing premise is that the printed enforcer gadgets force the values their names claim; in particular, the second copy of $S_u(c_i,y_i,y_i)$ and the second copy in $E_\forall(d_{i,k})$ must contain negated literals as the surrounding proof assumes, since identical copies would not force equality or truth and the yes-instance equivalences in statements 3.2.1 and 3.4.1 would fail.

Editorial extensions

If this is right

Balanced $\forall\exists$ 3-SAT-(2,2,2,2) being $\Pi_2^P$-complete means that a formula with four appearances per variable and equally many universal and existential variables already encodes the full difficulty of the second level of the polynomial hierarchy.
The (1,1,2,2) result shows that one universal appearance in each polarity is sufficient for $\Pi_2^P$-completeness, so the universal variables can be almost as constrained as the existential ones.
Monotone $\forall\exists$ NAE-3-SAT-(1,3) being $\Pi_2^P$-complete means linearity, monotonicity, one universal appearance, and three existential appearances do not weaken the quantified problem.
The NP-completeness of $\forall\exists$ 3-SAT-(s1,s2,t1,t2) with $s_1+s_2=1$ and $(t_1,t_2)\in\{(1,2),(2,1)\}$ shows that at the first level of the hierarchy the existential variables carry the hardness, and the universal quantifier becomes eliminable.
Monotone $\forall\exists$ NAE-3-SAT-(1,2) being polynomial-time solvable and $(s,2)$ variants being in co-NP marks the $(1,3)$ theorem as a tight boundary rather than an artifact of the reduction.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The same enforcer-plus-variable-splitting recipe should transfer to other quantified constraint satisfaction problems whose unquantified versions are NP-complete under bounded appearances; a natural next case is 1-in-3 SAT, whose NAE-style symmetry may again absorb a single universal appearance.
The sharp contrast between the two problems suggests that the not-all-equal predicate, because it is invariant under flipping all truth values, neutralizes the extra power that a second universal appearance gives ordinary quantified 3-SAT.
One testable extension the authors leave open is whether optimization versions of these $\Pi_2^P$-complete problems remain hard to approximate under the same appearance bounds.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The headline results are genuinely new: exact appearance-count thresholds for quantified 3-SAT and NAE-3-SAT that were not in Berman, Haviv, or Darmann-Döcker. The paper proves Balanced ∀∃ 3-SAT-(2,2,2,2) and (1,1,2,2) are Π_2^P-complete, pins down NP-completeness for the s1+s2=1 cases, and shows Monotone ∀∃ NAE-3-SAT-(1,3) is Π_2^P-complete for linear monotone formulas—plus matching positive results. The reduction strategy is standard enforcer work, but the gadgets are adapted to the quantified setting and the side results (co-NP, P) are correctly delimited. The authors re-derive the enforcer properties, so the circularity burden is low. For this subfield, it's a solid contribution.

The soft spot is the text I was given, not necessarily the PDF. The extracted formulas appear to lose negation bars in exactly the places where correctness depends on them. In Theorem 3.1 Step 3, the chain is rendered all-positive, which neither forces equality nor satisfies the (2,2,2,2) appearance counts; the intended implication chain with negated first literals repairs both. Theorem 3.2 Step 1 has Su(c_i,y_i,y_i) ∧ Su(c_i,y_i,y_i) duplicated, which would not enforce anything; the second copy needs negations. Theorem 3.4's E∀(d_i,k) is the same duplicated-clause issue. And in the first direction of Theorem 4.1's proof, setting e_i,k = β1(z_i) makes the clause (z_i,k ∨ e_i,k ∨ u_i,k) all-true when β1(z_i)=T and u_i,k=T; the existential should be ¬β1(z_i). These all look like typesetting or sign typos rather than flawed constructions—the intended gadgets are clear and the proofs otherwise hang together—but they are load-bearing enough that a referee needs the actual PDF to confirm.

Minor: the introduction cites Stockmeyer and Dahlhaus for the base completeness, but the correct attribution for ∀∃ NAE-3-SAT is Eiter-Gottlob (as stated in the preliminaries). Not a big deal, but sloppy.

If the PDF restores the overlines and fixes the e_i,k assignment, I'd expect the theorems to hold. This deserves a serious referee; the results are new and the approach is sound. I'd bring it to reading group only after checking the PDF.

Referee Report

5 major / 4 minor

Summary. The paper investigates quantified variants of 3-SAT and NAE-3-SAT with bounded variable appearances. Its main claims are that Balanced ∀∃ 3-SAT-(2,2,2,2) and Balanced ∀∃ 3-SAT-(1,1,2,2) are Π_2^P-complete, that Monotone ∀∃ NAE-3-SAT-(1,3) is Π_2^P-complete for linear formulas with at most one universal variable per clause, and that certain other variants are NP-complete, co-NP-complete, or polynomial-time solvable. The proofs use standard reductions from ∀∃ 3-SAT and ∀∃ NAE-3-SAT, along with enforcer gadgets, several of which are adapted from Berman et al. and from Darmann and Döcker.

Significance. If the results are correct, they provide tight bounded-appearance thresholds for quantified 3-SAT and quantified NAE-3-SAT, and the enforcer constructions could be useful for further work in the polynomial hierarchy. The positive results for Monotone ∀∃ NAE-3-SAT-(s,2) are also valuable. However, the version of the manuscript supplied for review has a systemic loss of negation bars in key formulas; as printed, several enforcers are identical to their complements or are otherwise not the gadgets the proofs require. The central claims are plausible and appear repairable, but the submitted text does not currently support them.

major comments (5)

[§2, Observation 2.1] The S-enforcer is printed as (ℓ1∨a∨b) ∧ (ℓ2∨b∨c) ∧ (ℓ3∨a∨c) ∧ (a∨b∨c) ∧ (a∨b∨c), so the fourth and fifth clauses are identical. With this formula, Observation 2.1 is false: for ℓ1=ℓ2=ℓ3=F, the assignment a=T, b=F, c=F satisfies all five clauses. The proof text says the first three clauses form a cyclic implication chain and that the fourth or fifth clause fails, which only works if the fifth clause is (¬a∨¬b∨¬c). Since x(2), E(x), Su, Q1, Q3, and E∀ are all built on this enforcer, the missing negation propagates into Theorems 3.1, 3.2, 3.4, and 4.1. As supplied, this is a load-bearing gap in the formal basis of the paper.
[§3.2, Theorem 3.1, Step 3] The chain clauses are printed as the all-positive cycle (w_{i,1}∨w_{i,2}) ∧ ... ∧ (w_{i,a}∨w_{i,1}). These clauses do not force w_{i,1}=...=w_{i,a}; for a=3, the assignment (T,T,F) satisfies every clause. The proof of statement 3.1.2 uses these clauses to conclude equality, so the intended clauses must be implications (¬w_{i,1}∨w_{i,2}), ..., (¬w_{i,a}∨w_{i,1}). The same issue affects the appearance counts: after Step 2 each w_{i,k} has one positive and one negative occurrence, and the chain must add exactly one positive and one negative occurrence to reach the claimed (2,2,2,2) counts. An analogous all-positive rendering occurs in Step 3 of Theorem 3.2, where the clauses must also be implications for the equality conclusion in statement 3.2.1.
[§3.2, Theorem 3.1, Step 4] The replacement of a 2-clause is printed as (ℓ1∨ℓ2∨u) ∧ E(u). Since E(u) forces u=T, the 3-clause is automatically satisfied and does not preserve the constraint of the original 2-clause. The contradiction argument in statement 3.1.2 for a complemented 2-clause also requires the literal u in the 3-clause to be negated. In addition, the printed version gives u three unnegated and one negated appearance, contradicting the claimed (2,2,2,2) count; using (ℓ1∨ℓ2∨¬u) instead restores exactly two unnegated and two negated appearances. Thus Step 4 must use (ℓ1∨ℓ2∨¬u) rather than (ℓ1∨ℓ2∨u).
[§3.2, Theorem 3.2, Step 1] Step 1 is printed with the duplicated pair Su(c_i,y_i,y_i) ∧ Su(c_i,y_i,y_i). The equality gadget needed for the equivalence in statement 3.2.1 must contain opposite polarities, for example Su(c_i,¬y_i,¬y_i) ∧ Su(¬c_i,y_i,y_i), in order to force y_i=c_i and to make the claimed counts come out: four unnegated and four negated appearances of y_i, and one unnegated and one negated appearance of c_i. As printed, the pair is either unsatisfiable for c_i=F (if the two copies are the same S(c,y,y) gadget) or does not give the stated counts. Consequently, the proof's assignment β4(y_i,k)=β4(c_i) is unsupported.
[§4.2, Theorem 4.1, proof of 4.1.1] In the forward direction of statement 4.1.1, the printed assignment sets β2(e_{i,k}) = β1(z_i). If β1(z_i)=T and the universal variable u_{i,k}=T, then the clause (z_{i,k}∨e_{i,k}∨u_{i,k}) is all true and hence not nae-satisfied, so the constructed formula Φ2 is not necessarily a yes-instance. The forward direction works only if e_{i,k} is assigned the negation of β1(z_i), or equivalently if the relevant clause contains a negated e-literal. This is a load-bearing gap in the proof of Theorem 4.1 as printed.

minor comments (4)

[§2, Preliminaries] The definition of a monotone Boolean formula is printed as "no clause contains an element in {x1,x2,...,xn}"; this should be the set of negated literals {¬x1,¬x2,...,¬xn}.
[§3.2, Theorem 3.1, proof of 3.1.2] The sentence "Let D be the clause obtained from C by applying Step 1" should refer to the complement of C, since the subsequent argument concludes that all literals of D evaluate to F; otherwise the argument is incoherent.
[§1, Introduction] The introduction attributes the Π_2^P-completeness of ∀∃ NAE-3-SAT to "Dahlhaus et al. [6]", but reference [6] is the Eiter-Gottlob report; the citation should be corrected.
[§3.1, Lemma 3.2] The proof of Lemma 3.2 contains the typo "Futhermore" instead of "Furthermore".

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the reductions start from externally established complete problems, and every gadget property used is proved in the paper rather than imported by self-citation.

full rationale

The paper's central reductions are anchored in externally established Pi_2^P-complete problems: forall-exists 3-SAT (Stockmeyer) and forall-exists NAE-3-SAT (Eiter-Gottlob), and in the NP-complete problem 3-SAT-(3) (Dahlhaus et al.). The bounded-appearance problems are not used as their own inputs; each logical equivalence is proved directly in the statements 3.1.1, 3.1.2, 3.2.1, 3.4.1, 4.1.1, 4.1.2, and 4.1.1 of Theorem 4.1. The gadget properties, including the S-enforcer, x(2), E(x), Q1, Q3, NEaux, EQ, NE, P1, and E-forall, are stated and proved in Observations 2.1-2.2, Observation 3.1, Lemmas 3.1-3.2, Observations 4.1-4.5, and Property (P). Although Section 4.1 credits the four monotone enforcers to Darmann and Docker [5], whose first author is also an author of the present paper, the formulas are reproduced in full and their properties are re-proved in the present text, and Proposition 4.1's transformation is fully specified and verified rather than imported as an unexamined result. Reference [2] (Bonet-Linz-St. John), also involving a co-author, is used only as background for the earlier consideration of constants in NAE-3-SAT and is not load-bearing for any completeness proof. Thus no claim reduces to a fitted parameter or to a self-citation chain. The extracted-text concerns about missing negation bars in certain rendered clauses are potential correctness defects in the proof presentation, not instances of circularity.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

The paper introduces enforcer gadgets, but these are proof constructions, not new physical or mathematical entities with independent falsifiable handles. No free parameters are fitted to data, and the axioms are standard prior results plus the correctness of the gadget constructions.

assumptions (7)

standard math Π_2^P-completeness of ∀∃ 3-SAT (Stockmeyer)
Used as the starting point for reductions in Section 3; proved in [16].
standard math Π_2^P-completeness of ∀∃ NAE-3-SAT (Eiter and Gottlob)
Used as the starting point for reductions in Sections 3 and 4; proved in [6].
standard math NP-completeness of 3-SAT-(3) (Dahlhaus et al.)
Used in Theorem 3.3 to prove NP-completeness of ∀∃ 3-SAT-(s1,s2,t1,t2) for s1+s2=1; from [4].
standard math Tovey's result that 3-SAT with each variable appearing at most four times is NP-complete, and with at most three times is trivial
Background cited in the introduction and used for comparison in Section 3.3.
standard math Porschen et al.'s linear-time algorithm for NAE-SAT with each variable appearing at most twice
Used in Proposition 4.2 to show MC-NAE-3-SAT-2 is in P; from [11].
domain assumption Correctness of the S-enforcer and related gadgets (Berman et al.)
The paper re-proves these properties in Observations 2.1 and 2.2, but the base gadgets originate in [1].
domain assumption Correctness of the Darmann-Döcker enforcers used in Section 4.1
The paper restates properties in Observations 4.1-4.5; the gadgets originate in [5], co-authored by one of the present authors.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Placing quantified variants of 3-SAT and Not-All-Equal 3-SAT in the polynomial hierarchy." pith.science (2026). https://pith.science/paper/G3FZMO7F

@misc{pith2026190805361,
  author       = {Pith},
  title        = {Pith review of: Placing quantified variants of 3-SAT and Not-All-Equal 3-SAT in the polynomial hierarchy},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/G3FZMO7F}},
  note         = {Machine review of arXiv:1908.05361}
}

abstract

The complexity of variants of 3-SAT and Not-All-Equal 3-SAT is well studied. However, in contrast, very little is known about the complexity of the problems' quantified counterparts. In the first part of this paper, we show that $\forall \exists$ 3-SAT is $\Pi_2^P$-complete even if (1) each variable appears exactly twice unnegated and exactly twice negated, (2) each clause is a disjunction of exactly three distinct variables, and (3) the number of universal variables is equal to the number of existential variables. Furthermore, we show that the problem remains $\Pi_2^P$-complete if (1a) each universal variable appears exactly once unnegated and exactly once negated, (1b) each existential variable appears exactly twice unnegated and exactly twice negated, and (2) and (3) remain unchanged. On the other hand, the problem becomes NP-complete for certain variants in which each universal variable appears exactly once. In the second part of the paper, we establish $\Pi_2^P$-completeness for $\forall \exists$ Not-All-Equal 3-SAT even if (1') the Boolean formula is linear and monotone, (2') each universal variable appears exactly once and each existential variable appears exactly three times, and (3') each clause is a disjunction of exactly three distinct variables that contains at most one universal variable. On the positive side, we uncover variants of $\forall \exists$ Not-All-Equal 3-SAT that are co-NP-complete or solvable in polynomial time.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages

[1]

Berman, M

P. Berman, M. Karpinski, and A. D. Scott (2003). Approxim ation hard- ness of short symmetric instances of MAX-3SAT. Electronic Colloquium on Computational Complexity , Report No. 49

work page 2003
[2]

M. L. Bonet, S. Linz, and K. St. John (2012). The complexit y of ﬁnding multiple solutions to betweenness and quartet compa tibility. IEEE/ACM Transactions on Computational Biology and Bioinform at- ics, 9(1), 273–285

work page 2012
[3]

S. A. Cook (1971), The complexity of theorem-proving pro cedures. In Proceedings of the Third Annual ACM Symposium on Theory of Co m- puting, 151–158. 34

work page 1971
[4]

Dahlhaus, D

E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Sey mour, and M. Yannakakis (1994). The complexity of multiterminal cuts . SIAM Journal on Computing , 23(4), 864–894

work page 1994
[5]

Darmann and J

A. Darmann and J. D¨ ocker (2019). On simpliﬁed NP-comple te variants of Not-All-Equal 3-SAT and 3-SAT. arXiv preprint arXiv:190 8.04198

work page 2019
[6]

Eiter and G

T. Eiter and G. Gottlob (1995). Note on the complexity of s ome eigen- vector problems. Technical Report CD-TR 95/89, Christian D oppler Laboratory for Expert Systems, TU Vienna

work page 1995
[7]

M. R. Garey and D. S. Johnson, Computers and Intractabili ty: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, 1979

work page 1979
[8]

Haviv, O

I. Haviv, O. Regev, and A. Ta-Shma (2007). On the hardness of sat- isﬁability with bounded occurrences in the polynomial-tim e hierarchy. Theory of Computing , 3, 45–60

work page 2007

Show all 17 references

[9]

Karpinski and K

M. Karpinski and K. Piecuch (2017). On vertex coloring wi thout monochromatic triangles. arXiv preprint arXiv:1710.0713 2

2017
[10]

Karpinski and K

M. Karpinski and K. Piecuch (2018). On vertex coloring w ithout monochromatic triangles. In: F. Fomin., V. Podolskii (eds) Computer Science – Theory and Applications. CSR 2018. Lecture Notes i n Com- puter Science, vol 10846. Springer, Cham

2018
[11]

Porschen, B

S. Porschen, B. Randerath, E. Speckenmeyer (2004). Lin ear time al- gorithms for some not-all-equal satisﬁability problems. I n: Giunchiglia E., Tacchella A. (eds) Theory and Applications of Satisﬁabi lity Test- ing. SAT 2003. Lecture Notes in Computer Science, vol 2919. S pri...

2004
[12]

Porschen, T

S. Porschen, T. Schmidt, E. Speckenmeyer and A. Wotzlaw (2014). XSAT and NAE-SAT of linear CNF classes. Discrete Applied Mathe- matics, 167, 1–14

2014
[13]

Schaefer (2001)

M. Schaefer (2001). Graph Ramsey theory and the polynom ial hierar- chy. Journal of Computer and System Sciences , 62, 290–322

2001
[14]

Schaefer and C

M. Schaefer and C. Umans (2002). Completeness in the pol ynomial- time hierarchy: A compendium. SIGACT News, 33(3), 32–49

2002
[15]

T. J. Schaefer (1978), The complexity of satisﬁablity p roblems. In Pro- ceedings of the Tenth annual ACM Symposium on Theory of Compu t- ing, 216–226

1978
[16]

L. J. Stockmeyer, The polynomial-time hierarchy. Theo retical Com- puter Science, 3 (1976), pp. 1–22. 35

1976
[17]

C. A. Tovey (1984). A simpliﬁed NP-complete satisﬁabil ity problem. Discrete Applied Mathematics , 8(1), 85–89. 36

1984

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

Berman, M

P. Berman, M. Karpinski, and A. D. Scott (2003). Approxim ation hard- ness of short symmetric instances of MAX-3SAT. Electronic Colloquium on Computational Complexity , Report No. 49

work page 2003

[2] [2]

M. L. Bonet, S. Linz, and K. St. John (2012). The complexit y of ﬁnding multiple solutions to betweenness and quartet compa tibility. IEEE/ACM Transactions on Computational Biology and Bioinform at- ics, 9(1), 273–285

work page 2012

[3] [3]

S. A. Cook (1971), The complexity of theorem-proving pro cedures. In Proceedings of the Third Annual ACM Symposium on Theory of Co m- puting, 151–158. 34

work page 1971

[4] [4]

Dahlhaus, D

E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Sey mour, and M. Yannakakis (1994). The complexity of multiterminal cuts . SIAM Journal on Computing , 23(4), 864–894

work page 1994

[5] [5]

Darmann and J

A. Darmann and J. D¨ ocker (2019). On simpliﬁed NP-comple te variants of Not-All-Equal 3-SAT and 3-SAT. arXiv preprint arXiv:190 8.04198

work page 2019

[6] [6]

Eiter and G

T. Eiter and G. Gottlob (1995). Note on the complexity of s ome eigen- vector problems. Technical Report CD-TR 95/89, Christian D oppler Laboratory for Expert Systems, TU Vienna

work page 1995

[7] [7]

M. R. Garey and D. S. Johnson, Computers and Intractabili ty: A Guide to the Theory of NP-Completeness, W. H. Freeman and Company, 1979

work page 1979

[8] [8]

Haviv, O

I. Haviv, O. Regev, and A. Ta-Shma (2007). On the hardness of sat- isﬁability with bounded occurrences in the polynomial-tim e hierarchy. Theory of Computing , 3, 45–60

work page 2007