PadhaikoAll subjects

Past exam question: 2082 Kartik (Back), Q5(a)

Theory of Computation · 3 marks

Open in the Padhaiko app

Topic: Time/Space Complexity; P, NP & NP-Complete

Question

Define 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 :

  1. 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.

  1. 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:

  1. (a candidate solution can be verified by a deterministic TM in polynomial time, or decided by a nondeterministic TM in polynomial time).
  2. 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.

Answer:

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).

All past exam questions for Theory of Computation