NP and EXP [cpsc/np-exp]

Claim: Np (complexity class) ⊆\subseteq Exp

Idea: For any L∈NPL \in NP, there is an NTM deciding LL in polynomial time. We can simulate it with a DTM that does the breadth-first search on the configuration tree. The tree has a number of nodes exponential in runtime of the NTM.

There are several open questions surrounding P (complexity class), Np (complexity class), and Exp:

  1. Is P≠N P\text{P} \neq \text{N P}, i.e. P⊂NP\text{P} \subset \text{NP}?
  2. Is NP≠EXP\text{NP} \neq \text{EXP}, i.e. NP⊂EXP\text{NP} \subset \text{EXP}?

The answer to either Q1 or Q2 is yes.

Proof: P⊆NP⊆EXP\text{P} \subseteq \text{NP} \subseteq \text{EXP}, yet by the time hierarchy theorem P≠EXP\text{P} \neq \text{EXP}. So either P≠NP\text{P} \neq \text{NP} or NP≠EXP\text{NP} \neq \text{EXP} (or both).