Theory of Computation

1. Which of the following is NOT an NP-Complete problem? TRE 4 Theory of computations Practice set 1 2. What is the computational complexity of the Halting Problem? TRE 4 Theory of computations Practice set 1 3. Which of the following is NOT a component of a Turing Machine? TRE 4 Theory of computations Practice set 1 4. Which of the following classes contains problems that can be solved in polynomial time? TRE 4 Theory of computations Practice set 1 5. Who proved that the general Halting Problem is undecidable? TRE 4 Theory of computations Practice set 1 6. Who introduced the concept of the Turing Machine? TRE 4 Theory of computations Practice set 1 7. What is the defining characteristic of an NP problem? TRE 4 Theory of computations Practice set 1 8. A decision problem is called decidable when: TRE 4 Theory of computations Practice set 1 9. What is the primary function of the read/write head in a Turing Machine? TRE 4 Theory of computations Practice set 1 10. Which theorem established Boolean Satisfiability (SAT) as the first NP-Complete problem? TRE 4 Theory of computations Practice set 1 11. Which of the following is an example of an undecidable problem? TRE 4 Theory of computations Practice set 1 12. Which symbol is commonly used to represent a blank cell on the tape of a Turing Machine? TRE 4 Theory of computations Practice set 1 13. Which of the following is an example of an NP-Hard problem? TRE 4 Theory of computations Practice set 1 14. What is the meaning of an undecidable problem in computer science? TRE 4 Theory of computations Practice set 1 15. What does the transition function of a Turing Machine determine? TRE 4 Theory of computations Practice set 1 16. Which condition must be satisfied for a problem to be NP-Complete? TRE 4 Theory of computations Practice set 1 17. Which mathematical model is commonly used to study the Halting Problem? TRE 4 Theory of computations Practice set 1 18. Which of the following best describes the tape of a standard Turing Machine? TRE 4 Theory of computations Practice set 1 19. Which of the following is a polynomial-time algorithm for finding the shortest path in a graph with non-negative edge weights? TRE 4 Theory of computations Practice set 1 20. Which of the following statements about decidable and undecidable problems is correct? TRE 4 Theory of computations Practice set 1 21. What is the role of the finite control unit in a Turing Machine? TRE 4 Theory of computations Practice set 1 22. If any one NP-Complete problem is solved in polynomial time, what will be the consequence? TRE 4 Theory of computations Practice set 1 23. What is the main technique used by Alan Turing to prove the undecidability of the Halting Problem? TRE 4 Theory of computations Practice set 1 24. Which of the following is the correct representation of a standard deterministic Turing Machine transition function? TRE 4 Theory of computations Practice set 1 25. Which of the following problems is a well-known NP-Complete decision problem? TRE 4 Theory of computations Practice set 1 26. Which of the following problems is decidable? TRE 4 Theory of computations Practice set 1 27. Which of the following is true about the initial state of a Turing Machine? TRE 4 Theory of computations Practice set 1 28. Which of the following statements about NP-Hard and NP-Complete problems is correct? TRE 4 Theory of computations Practice set 1 29. Which of the following is true about the Halting Problem? TRE 4 Theory of computations Practice set 1 30. Which of the following statements about a Universal Turing Machine is correct? TRE 4 Theory of computations Practice set 1