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

The QSAT problem, which asks to evaluate a quantified Boolean formula (QBF),is of fundamental interest in approximation, counting, decision, andprobabilistic complexity and is also considered the prototypical PSPACEcompleteproblem. As such, it has previously been studied under various structuralrestrictions (parameters), most notably parameterizations of the primal graphrepresentation of instances. Indeed, it is known that QSAT remainsPSPACE-complete even when restricted to instances with constant treewidth ofthe primal graph, but the problem admits a double-exponential fixed-parameteralgorithm parameterized by the vertex cover number (primal graph). However,prior works have left a gap in our understanding of the complexity of QSAT whenviewed from the perspective of other natural representations of instances, mostnotably via incidence graphs. In this paper, we develop structure-awarereductions which allow us to obtain essentially tight lower bounds for highlyrestricted instances of QSAT, including instances whose incidence graphs havebounded treedepth or feedback vertex number. We complement these lower boundswith novel algorithms for QSAT which establish a nearly-complete picture of theproblem's complexity under standard graph-theoretic parameterizations. We alsoshow implications for other natural graph representations, and obtain novelupper as well as lower bounds for QSAT under more fine-grainedparameterizations of the primal graph.

Structure-Aware Lower Bounds and Broadening the Horizon of Tractability for QBF