NEXPTIME: diferència entre les revisions

Sabem que

 

 

i també, pel teorema de la jerarquia del temps que

 

 

Si [[P (complexitat)|P]] = [[NP (Complexitat)|NP]], llavors NEXPTIME = EXPTIME, més precisament E ≠ NE si i només si existeixen llenguatges escassos a NP que no estan a P.<ref>{{Ref-publicació|cognom=Hartmanis|nom=J.|cognom2=Sewelson|nom2=V.|cognom3=Immerman|nom3=N.|article=Sparse sets in NP-P: Exptime versus nexptime|publicació=Proceedings of the fifteenth annual ACM symposium on Theory of computing|url=http://dl.acm.org/citation.cfm?id=800061.808769|data=1983-12-01|editorial=ACM|pàgines=382–391|doi=10.1145/800061.808769}}</ref>