P vs NP Problem §

---

Imagine an Oracle. Guesses and gets the right answer.

Build by (infinitely) many processors in a tree. If $2^n$ possible answers, tree is $n$ deep. A non-deterministic computer.

• P - the set of problems solvable in polynomial time.

• NP - the set of problems solvable in polynomial time on a non-deterministic computer.

  • Alternatively, verifiable in polynomial time on a deterministic computer.

• NP hard - any problem at least as hard as the hardest problems in NP.

• NP complete - a set of NP hard problems, all of which are equivalent.

• $P$ $\subseteq$ $NP$

• $NP$ $\ne$ $P$ has not been proven yet, but widely believed to be true.

See also §

• Problems