Q.1 What does the class P represent in computational complexity theory?
Problems solvable in polynomial time
Problems solvable in exponential time
Problems that are undecidable
Problems requiring non-determinism
Explanation - The class P contains decision problems that can be solved by a deterministic Turing machine in polynomial time.
Correct answer is: Problems solvable in polynomial time
Q.2 Which of the following is true about NP problems?
They can always be solved in linear time
Their solutions can be verified in polynomial time
They are unsolvable by Turing machines
They are equivalent to undecidable problems
Explanation - NP problems may not be efficiently solvable, but if given a solution, it can be verified in polynomial time by a deterministic Turing machine.
Correct answer is: Their solutions can be verified in polynomial time
Q.3 What does NP stand for?
Non-deterministic Polynomial time
Non-Polynomial
Not Possible
New Polynomial
Explanation - NP stands for Non-deterministic Polynomial time, meaning problems solvable in polynomial time by a non-deterministic Turing machine.
Correct answer is: Non-deterministic Polynomial time
Q.4 Which of the following best describes NP-complete problems?
They are problems in NP that are as hard as any other NP problem
They are solvable in constant time
They cannot be verified in polynomial time
They are undecidable
Explanation - An NP-complete problem is both in NP and as hard as any NP problem, meaning if one NP-complete problem is solved in polynomial time, all NP problems can be solved in polynomial time.
Correct answer is: They are problems in NP that are as hard as any other NP problem
Q.5 What is the significance of Cook’s theorem?
It proved that P = NP
It introduced NP-hard problems
It showed SAT is NP-complete
It showed undecidability of the Halting Problem
Explanation - Cook’s theorem proved that the Boolean satisfiability problem (SAT) is NP-complete, making it the first identified NP-complete problem.
Correct answer is: It showed SAT is NP-complete
Q.6 Which of the following problems is NP-complete?
Sorting
Boolean Satisfiability Problem (SAT)
Greatest Common Divisor (GCD)
Matrix Multiplication
Explanation - SAT is the first NP-complete problem proven by Cook’s theorem, unlike sorting or GCD which are in P.
Correct answer is: Boolean Satisfiability Problem (SAT)
Q.7 Which complexity class is known to contain problems that can be solved quickly and verified quickly?
P
NP
NP-complete
Undecidable
Explanation - Problems in P are solvable efficiently in polynomial time, and verification is also quick.
Correct answer is: P
Q.8 If a polynomial time algorithm is found for one NP-complete problem, what would it imply?
All problems are undecidable
P = NP
Nothing changes
P ≠ NP
Explanation - If one NP-complete problem is solvable in polynomial time, then every NP problem can be solved in polynomial time, proving P = NP.
Correct answer is: P = NP
Q.9 What is an NP-hard problem?
A problem that belongs to P
A problem harder than NP problems, but not necessarily in NP
A problem that cannot be verified
A problem that is undecidable
Explanation - NP-hard problems are at least as hard as NP problems but may not even be in NP (e.g., optimization problems).
Correct answer is: A problem harder than NP problems, but not necessarily in NP
Q.10 Which of the following is in P?
Traveling Salesman Problem
Sorting integers
3-SAT
Graph Coloring
Explanation - Sorting can be done in O(n log n), which is polynomial time. The others are NP-complete problems.
Correct answer is: Sorting integers
Q.11 Which of the following is NOT correct about P and NP?
P is a subset of NP
Every NP-complete problem is in NP
If P = NP, all NP problems can be solved efficiently
NP problems cannot be verified in polynomial time
Explanation - By definition, NP problems can be verified in polynomial time. The other statements are correct.
Correct answer is: NP problems cannot be verified in polynomial time
Q.12 The famous ‘P vs NP’ problem is concerned with:
Whether deterministic and non-deterministic polynomial time are equivalent
Whether undecidable problems can be solved
Whether NP-hard problems are decidable
Whether exponential algorithms are polynomial
Explanation - The central open problem is whether P = NP, i.e., whether deterministic and non-deterministic polynomial time classes are the same.
Correct answer is: Whether deterministic and non-deterministic polynomial time are equivalent
Q.13 Which of the following is an NP-complete problem?
Linear Programming
Knapsack Problem
Greatest Common Divisor
Binary Search
Explanation - The decision version of the Knapsack problem is NP-complete.
Correct answer is: Knapsack Problem
Q.14 Which complexity class contains undecidable problems?
P
NP
NP-complete
Outside NP
Explanation - Undecidable problems lie outside P and NP since no Turing machine can decide them.
Correct answer is: Outside NP
Q.15 What is the main challenge with NP-complete problems?
They cannot be verified
They are not solvable by computers
No known polynomial-time algorithms exist for them
They require infinite memory
Explanation - The main difficulty with NP-complete problems is that no polynomial-time algorithms are currently known.
Correct answer is: No known polynomial-time algorithms exist for them
Q.16 Which of the following belongs to NP but not known to be NP-complete?
Graph Coloring
SAT
Primality Testing (before AKS algorithm)
Traveling Salesman Problem
Explanation - Primality testing was long known to be in NP but not NP-complete until AKS algorithm placed it in P.
Correct answer is: Primality Testing (before AKS algorithm)
Q.17 What type of problem is the Halting Problem?
In P
In NP
NP-complete
Undecidable
Explanation - The Halting Problem is undecidable and lies outside P, NP, and NP-complete classes.
Correct answer is: Undecidable
Q.18 Which of the following is a property of NP-complete problems?
They can all be reduced to each other in polynomial time
They are solvable in O(1)
They are undecidable
They require non-deterministic exponential time
Explanation - By definition, NP-complete problems are inter-reducible in polynomial time.
Correct answer is: They can all be reduced to each other in polynomial time
Q.19 What does polynomial-time reduction mean?
Transforming one problem to another in polynomial time
Solving problems in O(1)
Checking primality
Reducing time complexity from exponential to polynomial
Explanation - Polynomial-time reduction means converting one problem into another in polynomial time, preserving difficulty.
Correct answer is: Transforming one problem to another in polynomial time
Q.20 If a problem is NP-hard and also in NP, then it is:
Undecidable
In P
NP-complete
Unsolvable
Explanation - By definition, NP-hard + in NP = NP-complete.
Correct answer is: NP-complete
Q.21 Which of the following is NOT NP-complete?
Subset Sum Problem
3-SAT
Traveling Salesman Decision Problem
Binary Search
Explanation - Binary Search is in P and not NP-complete. The others are classic NP-complete problems.
Correct answer is: Binary Search
Q.22 What does NP-hardness imply?
Problem is at least as hard as the hardest NP problems
Problem can be solved in logarithmic time
Problem belongs to P
Problem cannot be reduced
Explanation - NP-hard problems are at least as hard as NP problems but may not be in NP.
Correct answer is: Problem is at least as hard as the hardest NP problems
Q.23 Which is the first problem proven to be NP-complete?
Traveling Salesman Problem
Graph Coloring
Boolean Satisfiability Problem (SAT)
Subset Sum
Explanation - SAT was the first problem proven NP-complete by Cook’s theorem.
Correct answer is: Boolean Satisfiability Problem (SAT)
Q.24 Which statement is correct about P vs NP?
It is solved
It is one of the Millennium Prize Problems
It is irrelevant to computation
It proves NP problems are undecidable
Explanation - P vs NP is an unsolved Millennium Prize Problem by the Clay Mathematics Institute.
Correct answer is: It is one of the Millennium Prize Problems
Q.25 What is the time complexity class of matrix multiplication?
In P
In NP
NP-complete
Undecidable
Explanation - Matrix multiplication can be done in polynomial time, hence it belongs to class P.
Correct answer is: In P