Past exam question: 2082 Kartik (Back), Q5(a)
Open in the Padhaiko appDefine space and time complexity for the TM. Explain about NP-Complete problems.
Solution
Time and Space Complexity Definitions: Let be a deterministic Turing Machine that halts on all inputs of length :
- Time Complexity: The time complexity of is the maximum number of moves (steps) made by on any input of length :
Language class comprises all languages decidable by an time deterministic TM.
- Space Complexity: The space complexity of is the maximum number of distinct tape cells scanned by the tape head on any input of length :
Language class comprises all languages decidable within tape cells.
NP-Complete Problems: A decision problem is NP-Complete if it satisfies two conditions:
- (a candidate solution can be verified by a deterministic TM in polynomial time, or decided by a nondeterministic TM in polynomial time).
- is NP-Hard: Every problem is polynomial-time reducible to ().
Significance: NP-complete problems are the hardest problems in class NP. If a polynomial-time algorithm is discovered for any single NP-complete problem, then .
Classic Examples: Boolean Satisfiability (SAT / 3-SAT by the Cook–Levin Theorem), Traveling Salesperson Problem (decision version), Clique Problem, and Vertex Cover.
Time complexity is the maximum step count; space complexity is the maximum tape cells scanned on inputs of length . An NP-Complete problem is in NP and NP-Hard (every problem in NP reduces to it in polynomial time, e.g., 3-SAT, TSP).