it is not Non-polynomial! It is Nondeterministic polynomial!

Definition

It can be defined in two ways:

Nondeterministic TM

All languages that can be decided in Polynomial time using a Nondeterministic Turing Machine

Just memorize it and know that such definition exists. useless otherwise.

Polytime verifier

All languages that have a Certificate (of Polynomial length) which can be verified in Polynomial time.

Set of all problems for which you can check the correctness of an answer in Polynomial time

Relation to P

• Every problem in P is also in NP
  • By Definition 1: Every DTM is also an NTM.
  • By Definition 2: If it's easy to solve, instead of directly verifying the answer we can solve the problem again!
• We don't know if every problem NP is also in P
  • The famous P=NP problem!