Q.1 What does P stand for in complexity theory?
Polynomial Time
Parallel Processing
Probabilistic Time
Primitive Recursive
Explanation - P represents the set of decision problems solvable in polynomial time by a deterministic Turing machine.
Correct answer is: Polynomial Time
Q.2 Which class contains problems solvable by a nondeterministic Turing machine in polynomial time?
NP
P
PSPACE
L
Explanation - NP contains problems solvable in polynomial time by a nondeterministic Turing machine, or verifiable in polynomial time by a deterministic one.
Correct answer is: NP
Q.3 What is the major open problem in complexity theory?
P = NP?
Halting Problem
Church-Turing Thesis
Cook’s Theorem
Explanation - The P vs NP problem asks whether every problem verifiable in polynomial time can also be solved in polynomial time.
Correct answer is: P = NP?
Q.4 Cook’s Theorem established the NP-completeness of which problem?
SAT
3-SAT
Hamiltonian Cycle
Travelling Salesman
Explanation - Cook’s Theorem proved that the Boolean Satisfiability Problem (SAT) is NP-complete.
Correct answer is: SAT
Q.5 Which complexity class contains problems solvable with logarithmic space?
L
P
NP
PSPACE
Explanation - The class L includes problems solvable in logarithmic space on a deterministic Turing machine.
Correct answer is: L
Q.6 PSPACE represents problems solvable with:
Polynomial space
Polynomial time
Exponential space
Constant space
Explanation - PSPACE is the class of problems solvable by a Turing machine using polynomial space, regardless of time.
Correct answer is: Polynomial space
Q.7 Which of the following is known to be PSPACE-complete?
Quantified Boolean Formula (QBF)
SAT
3-SAT
Travelling Salesman
Explanation - QBF is a generalization of SAT and is PSPACE-complete.
Correct answer is: Quantified Boolean Formula (QBF)
Q.8 What is the relation between P and NP?
P ⊆ NP
NP ⊆ P
P = NP
P ∩ NP = ∅
Explanation - Every problem solvable in polynomial time is also verifiable in polynomial time, hence P ⊆ NP.
Correct answer is: P ⊆ NP
Q.9 Which of the following problems is NP-complete?
3-SAT
Addition
Sorting
Matrix Multiplication
Explanation - 3-SAT is a canonical NP-complete problem.
Correct answer is: 3-SAT
Q.10 Travelling Salesman Problem (decision version) belongs to which class?
NP-complete
P
L
PSPACE
Explanation - The decision version of TSP is NP-complete.
Correct answer is: NP-complete
Q.11 Which is the hardest class among the following?
EXPTIME
P
NP
PSPACE
Explanation - EXPTIME contains problems solvable in exponential time, which is generally harder than NP or PSPACE.
Correct answer is: EXPTIME
Q.12 Which class represents problems that can be solved in logarithmic space on a nondeterministic Turing machine?
NL
L
NP
PSPACE
Explanation - NL stands for Nondeterministic Logarithmic Space.
Correct answer is: NL
Q.13 Savitch’s Theorem relates which two complexity classes?
NL and L
NPSPACE and PSPACE
NP and P
P and EXPTIME
Explanation - Savitch’s Theorem states NPSPACE = PSPACE.
Correct answer is: NPSPACE and PSPACE
Q.14 Which of these is complete for the class NL?
ST-CONNECTIVITY
SAT
3-SAT
TSP
Explanation - ST-CONNECTIVITY is NL-complete.
Correct answer is: ST-CONNECTIVITY
Q.15 If a problem is NP-complete and it is found in P, then:
P = NP
NP ≠ P
It remains NP-complete
It becomes undecidable
Explanation - If any NP-complete problem is solvable in P, then P = NP.
Correct answer is: P = NP
Q.16 Which of these belongs to P?
Sorting
3-SAT
TSP
QBF
Explanation - Sorting can be solved in polynomial time using algorithms like Merge Sort or Quick Sort.
Correct answer is: Sorting
Q.17 What does NP-hard mean?
At least as hard as NP problems
In NP
In P
Undecidable
Explanation - NP-hard problems are as hard as the hardest problems in NP but not necessarily in NP themselves.
Correct answer is: At least as hard as NP problems
Q.18 Which is an NP-hard problem but not in NP?
Halting Problem
3-SAT
TSP (decision)
Hamiltonian Cycle
Explanation - Halting Problem is undecidable, so it is NP-hard but not in NP.
Correct answer is: Halting Problem
Q.19 Which complexity class includes undecidable problems?
Outside all recursive classes
NP
P
PSPACE
Explanation - Undecidable problems are not contained in P, NP, or PSPACE.
Correct answer is: Outside all recursive classes
Q.20 What is the complexity of matrix multiplication (naive method)?
O(n^3)
O(n^2)
O(n log n)
O(2^n)
Explanation - The naive matrix multiplication algorithm takes O(n^3) time.
Correct answer is: O(n^3)
Q.21 Which is faster: P or NP?
P
NP
They are equal
Depends on the problem
Explanation - P contains efficiently solvable problems, whereas NP problems may not be efficiently solvable.
Correct answer is: P
Q.22 Which of these problems is in P?
Checking primality
SAT
3-SAT
TSP (decision)
Explanation - AKS primality test shows primality can be checked in polynomial time.
Correct answer is: Checking primality
Q.23 What does the class EXP represent?
Exponential time problems
Extended polynomial
Extreme NP
Expanded memory
Explanation - EXP is the set of problems solvable in exponential time on a deterministic Turing machine.
Correct answer is: Exponential time problems
Q.24 Which class captures problems solvable in polynomial time by probabilistic algorithms with bounded error?
BPP
NP
RP
ZPP
Explanation - BPP (Bounded-error Probabilistic Polynomial time) represents such problems.
Correct answer is: BPP
Q.25 Which class captures problems solvable with zero-error probabilistic polynomial time?
ZPP
BPP
NP
RP
Explanation - ZPP represents problems solvable by randomized algorithms with zero error in expected polynomial time.
Correct answer is: ZPP