“Reasons to believe”

“Logicians on safari”

“Gödel’s Lost Letter and P=NP”

P ?= NP

“Simply stated, it asks whether every problem that can be quickly CHECKED by a computer can also be quickly SOLVED by one.”

Complexity Classes

P

polynomial

P is a class of problems solvable in polynomial times \(O(n^k)\) for some constant k

NP

non-deterministic polynomial

NP are class of problems that can be easily verified but hard to solve

NP is a class of problems verifiable in polynomial time

NP-Completeness

NP-complete: problem is in NP and is as hard as any problem in NP

NP-complete problems are the hardest problem in NP

Satisfiability is a NP-complete problem

##

If you can solve one, you can solve all

Decidability

Halting Problem

“A key part of the proof is a mathematical definition of a computer and program, which is known as a Turing machine; the halting problem is undecidable over Turing machines. It is one of the first cases of decision problems proven to be unsolvable.”

Reduction

Intractability

Very similar problems can have very different complexity

approximation

Quantum Complexity Theory

BQP

bounded-error quantum polynomial time