Theory of Computation · Unit 7 · 5 hrs
Undecidability and Intractability
Exam-focused notes for Undecidability and Intractability (Theory of Computation, CSC262): what the TU syllabus asks and how it has actually been tested, with 10 solved past questions from this unit.
What this unit covers
- Computational Complexity
- Time and Space complexity of A Turing Machine
- Intractability
- Complexity Classes
- Problem and its types: Absract, Decision, Optimization
- Reducibility
- Turing Reducible
- Circuit Satisfiability
- Cook's Theorem
- Undecidability
- Undecidable Problems: Post's Correspondence Problem, Halting Problem and its proof, Undecidable Problem about Turing Machines
Undecidable Problems
What is undecidable problem? Discuss about Post Correspondence Problem. [5]
--- A problem is undecidable if there is no Turing machine which will always halt in a finite amount of time to give an answer as 'yes' or 'no'. An undecidable problem has no algorithm to determine the answer for a given input. More formally, an undecidable...
Full solved answer →Complexity Classes
Differentiate between Class P and Class NP problem. Mention the transition function of DFA, NFA, and ε-NFA. [5]
--- Basis Class P Class NP --------- Full Form Polynomial Time Non-deterministic Polynomial Time Definition Set of decision problems solvable by a deterministic Turing machine in polynomial time O(n^k) Set of decision problems solvable by a non-deterministi...
Full solved answer →Explain about the complexity classes p, NP and NP-Complete. [5]
P (Polynomial Time) is the class of decision problems that can be solved by a deterministic Turing machine in polynomial time with respect to the input size n. - A problem belongs to P if there exists an algorithm that solves it in O(n^k) time for some cons...
Full solved answer →Problem and its types
How abstract, decision and optimization problems are different from each other? [5]
An abstract problem is a general, mathematical formulation of a computational problem. It defines a relationship between a set of problem instances (inputs) and a set of solutions (outputs), without restricting the form of the answer. - The solution can be ...
Full solved answer →Intractability
Write short notes (Any two): a) Big Oh, Big Omega and Big Theta b) Tractable and Intractable Problems c) Chomsky Hierarchy [5]
--- These are asymptotic notations used to describe the time or space complexity of algorithms as the input size n grows. --- Definition: f(n) = O(g(n)) if there exist positive constants c and n₀ such that: f(n) ≤ c · g(n) for all n ≥ n₀ - It gives the wors...
Full solved answer →Explain the term Intractability. Is SAT problem is intractable? Justify [5]
Definition: Intractability is a concept in computational complexity theory that classifies problems based on the time and space resources required to solve them. - Problems that can be solved within reasonable time and space constraints (i.e., in polynomial...
Full solved answer →What do you mean by tractable and Intractable problems? Explain with reference to TM. [5]
A problem is said to be tractable if it can be solved within reasonable time and space constraints. More formally, a problem is tractable if there exists an algorithm whose complexity (time and space) grows no more rapidly than a polynomial function of the ...
Full solved answer →What is intractability? Define time and space complexity of turing machine. [5]
Intractability is a concept used to classify problems that cannot be solved in polynomial time but instead require exponential time algorithms. - Problems that can be solved within reasonable time and space constraints are called tractable problems. - Probl...
Full solved answer →Time and Space complexity of A Turing Machine
What do you mean by computational Complexity? Explain about the time and space complexity of a Turing machine. [5]
The complexity of computational problems is discussed by choosing a specific abstract machine as a model of computation and considering how much resource a machine of that type requires for the solution of a given problem. - A Complexity Measure is a means ...
Full solved answer →Define complexity of a Turing machine. Explain about big Oh, big Omega and big Theta notation used for complexity measurement. [5]
The complexity of a Turing Machine refers to the measurement of resources (primarily time and space) used during a computation. When a Turing Machine answers a specific instance of a decision problem: - Time is measured as the number of moves made by the TM...
Full solved answer →Make Unit 7 stick
Practice CSC262 with flashcards & quizzes