Ruka hadi maudhui
The Lumenary
Shahada ya kwanza (juu)ComputationImepangwa

Computational complexity

Time and space complexity classes, P and NP, polynomial-time reductions, NP-completeness and the Cook–Levin theorem, and the status of the P versus NP problem.

math.comp.complexity-theory

Onyesha kila kinachohitajika kufikia mada hii

Somo la mada hii bado halijaandikwa. Muhtasari ulio hapa chini ni sehemu ya ramani ya mtaala na haujakaguliwa.

Inajengwa juu ya

ComputabilityAlgorithm design and analysis

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

Njia za kujifunza

Usomaji zaidi

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