EXP: A classe dos problemas que são reconhecidos por uma MTND (Máquina de Turing Não Determinística) em tempo exponencial.
PS (PSPACE): Pode-se considerar outra classe de problemas que inclui todos os problemas NP e parece incluir outros mais. A classe PS é definida como a classe de problemas onde uma MT usa um montante de espaço polinomial em função do tamanho da entrada, não importando a quantidade de tempo que ela usa.
P = co-P: Porque a classe P é fechada com relação à operação de complementação. Para obter Lc, basta inverter as saídas da MT. Ou seja, se uma linguagem L é decidível por uma MT polinomialmente limitada, então o seu complemento é decidido pela versão da MT que inverte as saídas.
P ⊆ NP: Pois uma MTND consegue simular uma MTD abrangendo a classe P, mas o contrário não é verdade.
NP ⊆ EXP: Pois uma MTD pode simular uma MTND; porém, ao realizar esta transformação, o não determinismo da MTND aumenta a complexidade, pois perde o paralelismo, tornando o tempo da solução exponencial (é sempre possível complicar) e, assim, tornando-se contida na classe EXP.
P = NP: Na teoria, ao mostrar que P = NP, significa que os problemas resolvidos em tempo polinomial por uma MTND podem ser resolvidos em tempo polinomial por uma MTD. Na prática, isso é difícil, pois uma MTND trabalha com paralelismo; ao tentar passar para MTD, a complexidade cresce, tornando-se exponencial (EXP), contrariando a hipótese P = NP.
NP = EXP: Na teoria, significa que há a possibilidade de um problema de uma MTD com tempo exponencial rodar em uma MTND em tempo polinomial. Na prática, isso existe para alguns casos, mas não para todos; há casos nos quais um problema decidível em tempo exponencial por uma MTD também será decidido em tempo exponencial por uma MTND.
P = EXP: Na teoria, um problema decidido por MTD em tempo exponencial pode ser reduzido para um tempo polinomial. Na prática, P está contido propriamente em EXP, pois os problemas de cunho exponencial de EXP não podem ser reduzidos para P, mesmo porque as duas complexidades usam a mesma máquina para tratar os problemas, no caso uma MTD.
NP ≠ co-NP: Na teoria, um problema e seu complemento não têm a mesma complexidade NP. Na prática, ao complementar um problema NP, ele se torna um problema co-NP, mas continua sendo decidido por uma MTND e continuará com a complexidade de tempo sendo polinomial, então NP = co-NP.
