¿cuál es la relación entre la clase de complejidad E(y EXP) y NP?

Question

Quiero saber si existe alguna relación entre la clase de complejidad E(y EXP) y NP.

También me gustaría saber si hay alguna $DTIME$ formulación o relaciones de $NTIME(O(n^k))$ donde n es el tamaño de la entrada y k es constante.

edit: por ejemplo, ¿contiene NP EXP?

Answer 1

Tenemos:

$$P \subseteq NP \subseteq PSPACE \subseteq EXP \,,$$

y $P \subsetneq EXP$ . Este último es el resultado del teorema de la jerarquía temporal; véase aquí . Por lo tanto, al menos una de las inclusiones anteriores es estricta, pero nadie sabe cuál.

Además conozca de Ronald V. Book's 1972 papel que $E \ne NP$ .