### P ⊆ NP

Wednesday, October 21st, 2009 - 5:24 pm - CodeTheory

P-complexity] The complexity class NP is the set of decision problems that can be solved by a non-deterministic Turing machine in polynomial time. [Turing machine]

C’mon, don’t tell me you know all about the P v.s. NP stuff, including NP-complete, NP-hard, Pseudo-polynomial time, NP-easy, NP-equivalent, and the whole Complexity Zoo.

In computational complexity theory, P […] is one of the most fundamental complexity classes. It contains all […] problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time. [*“So*`P = NP`

*means that for every problem that has an efficiently verifiable solution, we can find that solution efficiently as well.”*(**) [The Status of the P Versus NP Problem]***Lance Fortnow*C’mon, don’t tell me you know all about the P v.s. NP stuff, including NP-complete, NP-hard, Pseudo-polynomial time, NP-easy, NP-equivalent, and the whole Complexity Zoo.