Q.1 What does NP stand for in computational complexity theory?
Non-Polynomial
Non-deterministic Polynomial
Number Polynomial
Normal Polynomial
Explanation - NP stands for Non-deterministic Polynomial time, which refers to problems that can be verified in polynomial time.
Correct answer is: Non-deterministic Polynomial
Q.2 Which of the following is the first problem proven to be NP-complete?
Traveling Salesman Problem
Boolean Satisfiability Problem (SAT)
Knapsack Problem
Graph Coloring
Explanation - SAT was the first problem proven to be NP-complete by Cook's theorem in 1971.
Correct answer is: Boolean Satisfiability Problem (SAT)
Q.3 If a problem is NP-complete, it is:
Easier than NP
Harder than P
As hard as any problem in NP
Solvable in constant time
Explanation - NP-complete problems are the hardest problems in NP; if one can be solved in polynomial time, all NP problems can.
Correct answer is: As hard as any problem in NP
Q.4 What does it imply if P = NP?
All problems can be solved in logarithmic time
NP problems can be solved in polynomial time
No problem can be solved in polynomial time
Only NP-hard problems become solvable
Explanation - If P = NP, then every problem that can be verified in polynomial time can also be solved in polynomial time.
Correct answer is: NP problems can be solved in polynomial time
Q.5 Which of the following is an NP-hard problem?
Matrix Multiplication
Primality Testing
Travelling Salesman Problem (TSP)
Binary Search
Explanation - The decision version of TSP is NP-complete, and the optimization version is NP-hard.
Correct answer is: Travelling Salesman Problem (TSP)
Q.6 In approximation algorithms, the approximation ratio is defined as:
Optimal / Approximation
Approximation / Optimal
Min(Approximation, Optimal) / Max(Approximation, Optimal)
Max(Approximation, Optimal) / Min(Approximation, Optimal)
Explanation - The approximation ratio measures how close the approximation solution is to the optimal one.
Correct answer is: Max(Approximation, Optimal) / Min(Approximation, Optimal)
Q.7 Cook's Theorem is significant because it:
Shows NP = P
Proves SAT is NP-complete
Defines polynomial time algorithms
Introduces approximation theory
Explanation - Cook's theorem (1971) was the first to prove SAT is NP-complete, forming the basis of NP-completeness theory.
Correct answer is: Proves SAT is NP-complete
Q.8 Which class of problems is a subset of NP?
P
NP-hard
EXP
PSPACE
Explanation - P is a subset of NP because all problems solvable in polynomial time are also verifiable in polynomial time.
Correct answer is: P
Q.9 Graph Coloring is:
Polynomial time solvable
NP-complete for 3 or more colors
NP-hard only
Not related to NP
Explanation - The decision version of Graph Coloring with k ≥ 3 colors is NP-complete.
Correct answer is: NP-complete for 3 or more colors
Q.10 The Knapsack problem is:
Polynomial time solvable
NP-complete
Not in NP
PSPACE-complete
Explanation - The decision version of the Knapsack problem is NP-complete.
Correct answer is: NP-complete
Q.11 Which of the following is NOT NP-complete?
SAT
Hamiltonian Cycle
Minimum Spanning Tree
Subset Sum
Explanation - MST is solvable in polynomial time using algorithms like Kruskal's or Prim's, hence it is in P, not NP-complete.
Correct answer is: Minimum Spanning Tree
Q.12 An NP-hard problem is defined as:
At least as hard as any NP problem
Easier than P
In NP but not in P
Always undecidable
Explanation - NP-hard problems are at least as hard as NP problems but not necessarily in NP themselves.
Correct answer is: At least as hard as any NP problem
Q.13 Which approximation algorithm guarantees a solution within twice the optimal cost for metric TSP?
Greedy Algorithm
Christofides Algorithm
Nearest Neighbor
Dynamic Programming
Explanation - Christofides' algorithm achieves a 1.5-approximation for metric TSP.
Correct answer is: Christofides Algorithm
Q.14 Which of these is used as a proof technique to show NP-completeness?
Reduction
Induction
Recursion
Enumeration
Explanation - Problems are shown to be NP-complete by polynomial-time reductions from known NP-complete problems.
Correct answer is: Reduction
Q.15 Vertex Cover problem belongs to:
P
NP-complete
NP-hard but not NP
PSPACE
Explanation - Vertex Cover decision problem is NP-complete.
Correct answer is: NP-complete
Q.16 If a problem is both NP-hard and in NP, it is:
Undecidable
NP-complete
In P
PSPACE
Explanation - By definition, NP-complete problems are both in NP and NP-hard.
Correct answer is: NP-complete
Q.17 The approximation ratio of a polynomial-time approximation algorithm is always:
≥ 1
≤ 1
= 0
= ∞
Explanation - The approximation ratio compares approximation cost with optimal; it is always at least 1.
Correct answer is: ≥ 1
Q.18 Which problem is often reduced to prove others are NP-complete?
Sorting
SAT
MST
Binary Search
Explanation - SAT is the classic NP-complete problem used for reductions.
Correct answer is: SAT
Q.19 In which case can approximation algorithms be very useful?
When the problem is in P
When the problem is NP-hard
When the problem is undecidable
When problem has no optimal solution
Explanation - Approximation algorithms provide near-optimal solutions for NP-hard problems where exact solutions are impractical.
Correct answer is: When the problem is NP-hard
Q.20 Subset Sum problem is:
NP-complete
In P
NP-hard but not in NP
PSPACE-complete
Explanation - Subset Sum decision problem is NP-complete.
Correct answer is: NP-complete
Q.21 Approximation schemes (PTAS, FPTAS) are designed for:
Polynomial-time solvable problems
Undecidable problems
Optimization NP-hard problems
Recursive functions
Explanation - Approximation schemes provide solutions arbitrarily close to optimal for optimization problems that are NP-hard.
Correct answer is: Optimization NP-hard problems
Q.22 3-SAT is:
In P
NP-complete
NP-hard but not in NP
Undecidable
Explanation - 3-SAT is NP-complete and widely used in reductions.
Correct answer is: NP-complete
Q.23 Which of these is known to have a Polynomial Time Approximation Scheme (PTAS)?
Knapsack Problem
Graph Coloring
3-SAT
Travelling Salesman Problem (general)
Explanation - The Knapsack problem admits a Fully Polynomial Time Approximation Scheme (FPTAS).
Correct answer is: Knapsack Problem
Q.24 Clique decision problem is:
In P
NP-complete
NP-hard only
Not in NP
Explanation - The Clique decision problem is NP-complete.
Correct answer is: NP-complete
Q.25 Which one is true for NP-complete problems?
All NP-complete problems can be solved in O(1)
If one NP-complete problem is in P, then P=NP
They are all undecidable
They are not verifiable in polynomial time
Explanation - The definition of NP-completeness implies that solving one in polynomial time solves all NP problems in polynomial time.
Correct answer is: If one NP-complete problem is in P, then P=NP