English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Open

Presents the pdf analysis as premium feature

PDF Analysis

Insights

Presents the summarisation as premium feature

Summarisation

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

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 theproblems' quantified counterparts. In the first part of this paper, we showthat $\forall \exists$ 3-SAT is $\Pi_2^P$-complete even if (1) each variableappears exactly twice unnegated and exactly twice negated, (2) each clause is adisjunction of exactly three distinct variables, and (3) the number ofuniversal variables is equal to the number of existential variables.Furthermore, we show that the problem remains $\Pi_2^P$-complete if (1a) eachuniversal variable appears exactly once unnegated and exactly once negated,(1b) each existential variable appears exactly twice unnegated and exactlytwice negated, and (2) and (3) remain unchanged. On the other hand, the problembecomes NP-complete for certain variants in which each universal variableappears 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 variableappears exactly once and each existential variable appears exactly three times,and (3') each clause is a disjunction of exactly three distinct variables thatcontains at most one universal variable. On the positive side, we uncovervariants of $\forall \exists$ Not-All-Equal 3-SAT that are co-NP-complete orsolvable in polynomial time.

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