Computational complexity

Inajengwa juu ya

Masharti ya awali ya lazima 25 (hadi chini kabisa)

Utajifunza

• Define P and NP and place standard problems in them.
• Prove NP-completeness of problems such as 3-SAT, vertex cover or graph 3-colouring by reductions.
• Explain what is known and unknown about P versus NP, and why cryptography relies on unproved hardness assumptions.

Fasili

• P is the class of decision problems solvable in polynomial time by a deterministic Turing machine.
• NP is the class of decision problems whose yes-instances have certificates that can be verified in polynomial time.
• A problem is NP-complete if it is in NP and every problem in NP reduces to it in polynomial time.

Nadharia

• Cook–Levin: Boolean satisfiability (SAT) is NP-complete.
• P ⊆ NP ⊆ PSPACE ⊆ EXPTIME, and P ≠ EXPTIME by the time hierarchy theorem.
• Whether P = NP is open; it is one of the Clay Mathematics Institute's Millennium Prize Problems.

Mawazo potofu ya kawaida

• Thinking NP stands for 'not polynomial'; it stands for nondeterministic polynomial time.
• Believing NP-complete problems cannot be solved in practice; many large instances are solved routinely.

Ugunduzi wa hiari

• Proof theory Proof complexity asks how long proofs of propositional tautologies must be; NP ≠ coNP holds if and only if no propositional proof system has polynomial-size proofs of all tautologies (Cook–Reckhow).
• ← Propositional logic and truth tables
• ← Algorithms, correctness and efficiency
• ← Cryptography
• ← Graph theory
• ← The probabilistic method

Njia za kujifunza

• Computer science and formal methods

Usomaji zaidi

• Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach (2009)
• Michael Sipser, Introduction to the Theory of Computation (1996)