Q.1 Which of the following best describes a problem in the class P?
A problem that can be solved in polynomial time
A problem that cannot be solved in polynomial time
A problem for which a solution can be verified in polynomial time
A problem that is undecidable
Explanation - Class P consists of decision problems that can be solved by a deterministic Turing machine in polynomial time.
Correct answer is: A problem that can be solved in polynomial time
Q.2 What does NP stand for in computational complexity theory?
Non-Polynomial
Nondeterministic Polynomial time
Not Possible
Non-Provable
Explanation - NP stands for Nondeterministic Polynomial time, referring to decision problems where a proposed solution can be verified in polynomial time.
Correct answer is: Nondeterministic Polynomial time
Q.3 Which of the following is true about NP-complete problems?
All NP-complete problems are in P
If one NP-complete problem is in P, then P = NP
They are all undecidable
They cannot be reduced to each other
Explanation - NP-complete problems are the hardest problems in NP. If any NP-complete problem is solved in polynomial time, all problems in NP can be solved in polynomial time.
Correct answer is: If one NP-complete problem is in P, then P = NP
Q.4 Which of the following statements defines a polynomial-time reduction between two problems A and B?
A can be solved using B in exponential time
A can be transformed into B in polynomial time
B can be verified using A in polynomial time
A and B are undecidable
Explanation - A polynomial-time reduction from A to B means that any instance of problem A can be transformed into an instance of problem B using a polynomial-time algorithm.
Correct answer is: A can be transformed into B in polynomial time
Q.5 What is the relationship between NP-hard and NP-complete problems?
NP-complete problems are a subset of NP-hard problems
NP-hard problems are a subset of NP-complete problems
They are completely unrelated
NP-hard problems are easier than NP-complete problems
Explanation - All NP-complete problems are NP-hard, but NP-hard problems may not necessarily be in NP (i.e., may not be decision problems).
Correct answer is: NP-complete problems are a subset of NP-hard problems
Q.6 Which problem is a classic example of an NP-complete problem?
Finding the greatest common divisor
Boolean satisfiability (SAT)
Binary search in a sorted array
Matrix multiplication
Explanation - The Boolean satisfiability problem (SAT) was the first problem proven to be NP-complete (Cook-Levin theorem).
Correct answer is: Boolean satisfiability (SAT)
Q.7 What does it mean if a problem is undecidable?
It has no solution
It cannot be solved by any algorithm
It can be solved in exponential time
It can be reduced to a P problem
Explanation - An undecidable problem is one for which no algorithm can determine the answer for all instances.
Correct answer is: It cannot be solved by any algorithm
Q.8 Which of the following is true for the class co-NP?
It contains the complements of NP problems
It contains all problems solvable in polynomial time
It is the same as P
It is undecidable
Explanation - co-NP consists of decision problems where the complement of the problem is in NP.
Correct answer is: It contains the complements of NP problems
Q.9 What is the significance of Cook-Levin theorem?
It proves P = NP
It shows that SAT is NP-complete
It proves that P ⊂ NP
It defines Turing machines
Explanation - The Cook-Levin theorem established that SAT (Boolean satisfiability) is NP-complete, providing the foundation for NP-completeness theory.
Correct answer is: It shows that SAT is NP-complete
Q.10 Which of the following describes a problem in the class PSPACE?
Solvable in polynomial space
Solvable in polynomial time
Solvable in exponential time
Undecidable
Explanation - PSPACE consists of decision problems solvable by a Turing machine using polynomial amount of memory, regardless of time.
Correct answer is: Solvable in polynomial space
Q.11 Which of the following is true about EXPTIME problems?
They can be solved in polynomial time
They require exponential time in the worst case
They are undecidable
They are all NP-complete
Explanation - EXPTIME problems are decision problems solvable by a deterministic Turing machine in exponential time.
Correct answer is: They require exponential time in the worst case
Q.12 If a problem A reduces to problem B in polynomial time, which statement is correct?
Solving B helps in solving A
Solving A helps in solving B
A and B are unrelated
Both are undecidable
Explanation - If A ≤p B (A reduces to B), an efficient solution to B can be used to efficiently solve A.
Correct answer is: Solving B helps in solving A
Q.13 What does the term 'NP-intermediate' refer to?
Problems that are in P
Problems that are neither in P nor NP-complete
Problems that are undecidable
Problems that are NP-hard but not NP-complete
Explanation - Ladner's theorem states that if P ≠ NP, there exist problems in NP that are neither in P nor NP-complete, called NP-intermediate problems.
Correct answer is: Problems that are neither in P nor NP-complete
Q.14 Which of the following statements is true about reductions?
Reductions always decrease complexity
They are used to prove hardness of problems
They can only be used for P problems
They are irrelevant to NP-complete problems
Explanation - Polynomial-time reductions are used to demonstrate that solving one problem is at least as hard as another, often for proving NP-completeness.
Correct answer is: They are used to prove hardness of problems
Q.15 What is the difference between NP-hard and NP-complete problems?
NP-hard problems are always solvable in polynomial time
NP-complete problems are in NP, NP-hard problems may not be
NP-hard problems are easier than NP-complete
There is no difference
Explanation - NP-hard includes problems at least as hard as NP-complete problems; NP-complete problems are a subset of NP-hard that are also in NP.
Correct answer is: NP-complete problems are in NP, NP-hard problems may not be
Q.16 Which complexity class contains all decidable problems?
RE
R
NP
PSPACE
Explanation - Class R (Recursive) consists of all problems that are decidable by a Turing machine.
Correct answer is: R
Q.17 Which of the following is undecidable?
Halting problem
Binary search
Sorting an array
Graph connectivity
Explanation - The Halting problem, which determines if a Turing machine halts on a given input, is undecidable.
Correct answer is: Halting problem
Q.18 Which class contains all problems whose solutions can be verified in polynomial time?
P
NP
PSPACE
EXPTIME
Explanation - Class NP contains problems for which proposed solutions can be verified in polynomial time by a deterministic Turing machine.
Correct answer is: NP
Q.19 Which of the following best describes a Turing reduction?
Using an oracle to solve one problem using another
Transforming a problem into another in polynomial time
Solving a problem in polynomial space
Proving undecidability
Explanation - Turing reductions use an oracle (a black box) to solve one problem using solutions to another problem, possibly multiple times.
Correct answer is: Using an oracle to solve one problem using another
Q.20 Which of the following is a property of EXPSPACE problems?
They can be solved in exponential space
They are in P
They are undecidable
They can be solved in polynomial time
Explanation - EXPSPACE is the class of problems solvable using an amount of memory that is exponential in the input size.
Correct answer is: They can be solved in exponential space
Q.21 Which problem class is closed under complement?
P
NP-complete
EXPTIME
Undecidable problems
Explanation - Class P is closed under complement, meaning if a problem is in P, so is its complement.
Correct answer is: P
Q.22 Which of the following is true if a problem is NP-complete?
It is the easiest problem in NP
All problems in NP reduce to it in polynomial time
It is undecidable
It requires exponential space
Explanation - NP-complete problems are the hardest problems in NP; every problem in NP can be polynomial-time reduced to an NP-complete problem.
Correct answer is: All problems in NP reduce to it in polynomial time
Q.23 What does the notation A ≤p B signify?
A is easier than B
Problem A reduces to problem B in polynomial time
A and B are in P
A and B are NP-complete
Explanation - A ≤p B indicates a polynomial-time reduction from problem A to problem B.
Correct answer is: Problem A reduces to problem B in polynomial time
Q.24 Which class contains decision problems solvable by a nondeterministic Turing machine using polynomial space?
PSPACE
NP
EXPTIME
R
Explanation - PSPACE includes all decision problems solvable in polynomial space, regardless of time, by a deterministic or nondeterministic Turing machine.
Correct answer is: PSPACE