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/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Large complexity classes, like the exponential time hierarchy, receivedlittle attention in terms of finding complete problems. In this work ageneralization of propositional logic is investigated which fills this gap withthe introduction of Boolean higher-order quantifiers or equivalently BooleanSkolem functions. This builds on the important results of Wrathall andStockmeyer regarding complete problems, namely QBF and QBF-k, for thepolynomial hierarchy. Furthermore it generalizes the Dependency QBF problemintroduced by Peterson, Reif and Azhar which is complete for NEXP, the firstlevel of the exponential hierarchy. Also it turns out that the hardness resultsdo not collapse at the consideration of conjunctive and disjunctive normalforms, in contrast to plain QBF.

Complete Problems of Propositional Logic for the Exponential Hierarchy