Fundamentals of complexity theory

Explore tractable and intractable problems, polynomial time algorithms, and the contrast between deterministic and non deterministic algorithms with examples like merge sort and traveling salesman.

Present four complexity classes—P, NP, NP-hard, and NP-complete—and show that P is solvable in polynomial time, NP verifiable in polynomial time, with NP-hard outside and NP-complete when both apply.

Explore reducibility in complexity theory, performing polynomial-time reductions that map instances between languages to establish NP-completeness, via reduction functions and reduction algorithms.

Investigate whether P equals NP by contrasting problems solvable in polynomial time with those verifiable in polynomial time; learn how NP-complete problems would imply P equals NP.

Assess whether a boolean circuit with and, or, and not gates is satisfiable by finding an input that yields output 1, the first NP-complete problem proved by Cook.

The circuit satisfiability problem asks whether a boolean circuit can yield 1. Cook proved this NP-complete problem is the first of its kind, and verification runs in polynomial time.

Explain how a boolean formula in 3CNF with literals in each clause joined by or and clauses joined by and defines 3CNF SAT and its NP-complete status via reduction.

Identify whether a graph contains a clique of size k and show that the clique problem is NP-complete via a reduction from the 3CNF-SAT problem.

Explore the vertex cover problem, define a vertex cover, verify and reduce to show NP-completeness, and demonstrate a reduction from the clique problem using graph complementation.

Explore the Hamiltonian cycle problem, a graph decision question about a cycle visiting every vertex. Learn about Belman's dynamic programming approach, its non-polynomial complexity, NP-completeness, and vertex cover reduction.

Explore the traveling salesman problem on graphs, where a tour visits every city exactly once, returns to the start, and costs at most k, prove NP-complete via Hamiltonian cycle reduction.