Theory of Computation – Multiple Choice Questions (MCQs)

1. 25. What is the Halting Problem?

   • A. The problem of determining whether a given Turing Machine will eventually halt on a given input
   • B. The problem of finding the shortest path in a graph
   • C. The problem of determining if a number is prime
   • D. The problem of compiling a program

2. 26. What is the class P?

   • A. The class of decision problems that can be solved by a deterministic Turing Machine in polynomial time
   • B. The class of decision problems that can be solved by a non-deterministic Turing Machine in polynomial time
   • C. The class of all decidable problems
   • D. The class of undecidable problems

3. 27. What is the class NP?

   • A. The class of decision problems that can be solved by a deterministic Turing Machine in polynomial time
   • B. The class of decision problems for which a given solution can be verified in polynomial time by a deterministic Turing Machine
   • C. The class of all decidable problems
   • D. The class of undecidable problems

4. 28. What is NP-completeness?

   • A. A property of a problem that is in NP and is as hard as any other problem in NP
   • B. A property of a problem that can be solved in polynomial time
   • C. A property of an undecidable problem
   • D. A property of a regular language

5. 29. If a problem is NP-complete, it means:

   • A. It can be solved in polynomial time
   • B. Any problem in NP can be reduced to it in polynomial time
   • C. It is undecidable
   • D. It is a regular language problem

6. 30. Which of the following is a well-known NP-complete problem?

   • A. Sorting
   • B. Searching
   • C. Traveling Salesperson Problem
   • D. Addition

7. 31. What is a reduction in computational complexity?

   • A. A way to transform one problem into another problem such that a solution to the second problem can be used to solve the first problem
   • B. A way to simplify a problem
   • C. A way to make an algorithm run faster
   • D. A way to prove a problem is undecidable

8. 32. If problem A can be reduced to problem B in polynomial time, and B is in P, then:

   • A. A is also in P
   • B. A is NP-complete
   • C. A is undecidable
   • D. B is NP-complete

9. 33. If problem A can be reduced to problem B in polynomial time, and A is NP-complete, then:

   • A. B is also in P
   • B. B is NP-complete
   • C. B is undecidable
   • D. A is in P

10. 34. What is the P vs NP problem?

    • A. The question of whether every problem whose solution can be quickly verified can also be quickly solved
    • B. The question of whether Turing Machines are the most powerful model of computation
    • C. The question of whether all undecidable problems are equally hard
    • D. The question of whether regular languages are a subset of context-free languages

11. 35. What is the significance of the P vs NP problem?

    • A. It has major implications for the existence of efficient algorithms for many important problems
    • B. It determines the power of finite automata
    • C. It defines the limits of regular expressions
    • D. It is only a theoretical curiosity with no practical impact

12. 36. What is space complexity?

    • A. The amount of memory space required by an algorithm to run
    • B. The amount of time required by an algorithm to run
    • C. The number of lines of code in an algorithm
    • D. The number of inputs an algorithm can handle