Unit 4: Unsolvability and complexity
Theory of Computation notes · PTU syllabus (PGCA1927)
On this page
Unit summary
Some problems cannot be solved by any algorithm, and many solvable ones are too costly. This unit covers unsolvable problems, the halting problem, Post's correspondence problem, unsolvable problems for context-free languages, measuring and classifying complexity, and tractable and intractable problems.
After this unit you can
- Prove the halting problem undecidable
- Explain Post's correspondence problem and reductions
- Identify undecidable problems about CFLs
- Classify problems by complexity: P, NP, NP-complete
PTU syllabus topics
- Unsolvable problems
- the halting problem
- Post correspondence problem
- unsolvable problems for context-free languages
- measuring and classifying complexity
- tractable and intractable problems
Decidable
A TM always halts with yes or no
Is a string in a regular language?
Undecidable
No algorithm exists
Halting problem, Post correspondence
P
Solvable in polynomial time
Sorting, shortest path
NP-complete
Hardest problems in NP
SAT, travelling salesman (decision)
Topic 1
Unsolvable problems
- A problem is decidable if some TM always halts with the correct yes or no answer; otherwise it is undecidable. Reduction: if A reduces to B and A is undecidable, then B is undecidable.
Topic 2
The halting problem
- 1Assume a TM H decides whether M halts on w
- 2Build D: on input M, run H on (M, M); if H says "halts", loop forever; otherwise halt
- 3Run D on its own description
- 4If D halts, H said it does not halt; if D loops, H said it halts
- 5Contradiction — so H cannot exist
- Rice's theorem: every non-trivial property of the language recognised by a TM is undecidable (e.g., "does M accept any string?").
Topic 3
Post's correspondence problem
- PCP: given pairs of strings (x1, y1), …, (xn, yn), is there a sequence of indices i1 … ik with xi1 … xik = yi1 … yik? PCP is undecidable and is used to prove other problems undecidable.
Example
Pairs (a, ab), (bb, b): choose 1 then 2 → top "a" + "bb" = "abb", bottom "ab" + "b" = "abb" — a solution.
Topic 4
Unsolvable problems for context-free languages
- Ambiguity
- Is a given CFG ambiguous?
- Equivalence
- Do two CFGs generate the same language?
- Universality
- Does a CFG generate all of Σ∗?
- Intersection emptiness
- Is the intersection of two CFLs empty?
- Regularity
- Is a CFL regular?
- Decidable questions: emptiness, finiteness and membership of a CFL.
Topic 5
Measuring and classifying complexity
- Time complexity of a TM: the maximum number of steps on inputs of length n; space complexity: the maximum tape cells used. Expressed with big-O notation.
P
Decidable in polynomial time by a deterministic TM
Sorting, shortest paths, primality testing
NP
Solutions verifiable in polynomial time (decidable by a non-deterministic TM in polynomial time)
SAT, Hamiltonian cycle, subset sum
NP-complete
In NP and every NP problem reduces to it in polynomial time
SAT (Cook–Levin), 3-SAT, vertex cover, travelling salesperson (decision)
NP-hard
At least as hard as NP-complete problems; need not be in NP
Optimisation TSP, halting problem
- P versus NP is the central open question: if any NP-complete problem has a polynomial algorithm, then P = NP.
Topic 6
Tractable and intractable problems
- Tractable: solvable in polynomial time — practical for large inputs. Intractable: no known polynomial algorithm (exponential growth) — e.g., 2ⁿ steps for n = 100 is beyond any computer.
- Coping with intractability: approximation algorithms, heuristics and metaheuristics, special cases, randomised algorithms, and exact methods for small inputs (branch and bound).
Key terms
- Undecidable problem
- Problem with no algorithm that always halts with the answer
- Halting problem
- Deciding whether a program halts on an input
- Reduction
- Transforming one problem into another
- NP-complete
- Hardest problems in NP
- Tractable problem
- Problem solvable in polynomial time
Quick revision
- Decidable vs undecidable; reductions; Rice's theorem.
- Halting problem proof by diagonalisation.
- PCP and its use.
- Undecidable CFG questions: ambiguity, equivalence, universality.
- Time and space complexity; P, NP, NP-complete, NP-hard; P vs NP; tractable vs intractable.
Important exam questions
Practice questions written to the PTU exam pattern for this unit's syllabus: short answers (Section A style) and long answers (Sections B and C style).
Short-answer questions
- Q1.What is an undecidable problem?
- Q2.State the halting problem.
- Q3.What is Post's correspondence problem?
- Q4.Name two undecidable problems about CFGs.
- Q5.Define the class NP.
- Q6.What does NP-complete mean?
Long-answer questions
- Q1.Prove that the halting problem is undecidable.
- Q2.Explain Post's correspondence problem with an example.
- Q3.Explain unsolvable problems for context-free languages.
- Q4.Explain P, NP, NP-complete and NP-hard problems.
Stuck on this unit?
Message SBS on WhatsApp for help with Theory of Computation, or to ask about studying M.Sc IT at Synetic.