Az a kérdés, hogy az NP osztály egyenlő lehet-e az EXPTIME osztállyal, a számítási komplexitáselmélet alapvető szempontjaiba nyúlik bele. A lekérdezés átfogó megválaszolásához elengedhetetlen, hogy megértsük ezeknek a komplexitási osztályoknak a definícióit és tulajdonságait, a köztük lévő kapcsolatokat és az ilyen egyenlőség következményeit. Definíciók és tulajdonságok