PyQdeck LogoPyQdeckSubjectsSyllabusBlog
Back to the 2025 paper

Module 4: Tractable and Intractable Problems

20252m

The Quantified Boolean Formula problem is a canonical complete problem for which of the following complexity classes?

(i) NP
(ii) P
(iii) PSPACE
(iv) co-NP

Search GoogleAsk AI
Worked SolutionAI Assisted

Answer: (iii) PSPACE

Explanation:

  • QBF (Quantified Boolean Formula): given ∃x1∀x2∃x3…ϕ(x1,…,xn)\exists x_1 \forall x_2 \exists x_3 \dots \phi(x_1,\dots,x_n), is it true? It extends SAT with quantifiers.
  • QBF is PSPACE-complete (Stockmeyer-Meyer 1973). SAT is NP-complete; QBF with unbounded alternation captures polynomial-space computation.
  • Complete for PSPACE under polytime reductions → canonical PSPACE-complete problem.
  • NP is ∃\exists-only; co-NP is ∀\forall-only; PSPACE allows both via alternation.

Correct choice: (iii) PSPACE

Similar questions

Design and Analysis of Algorithms Which complexity class contains problems for which a given solution can be verified in polynomial time by a deterministic Turing machine? (i) Class P (ii) Class NP (iii) Class NP-Hard (iv) Class Undecidable20252mDesign and Analysis of Algorithms What is the relationship between NP and P complexity classes? (i) P is a subset of NP (ii) NP is a subset of P (iii) P and NP are equivalent (iv) P and NP are disjoint sets20232mDesign & Analysis of AlgorithmsHamiltonian path problem is ______? - (i) NP Problem - (ii) NP Complete - (iii) P Class Problem - (iv) N Class Problem20242mDesign and Analysis of Algorithms Which one is true of the following (i) all NP hard problems are NP complete (ii) all NP complete problems are NP hard (iii) some NP complete problems are NP hard (iv) None of these20222m
PreviousWhat is the approximation ratio (or performance ratio) of the greedy algorithm for the Vertex Cover problem? (i) 2 (ii) 1.5 (iii) ln n (iv) 1NextWrite and explain the Cook's theorem.
Official AppAndroid App

PYQDeck for Android

Solve BEU previous-year exam papers anywhere, anytime. Fast search, offline paper viewing, and step-by-step solutions designed specifically for your phone.

Get on Google Play