NEXPTIME: diferència entre les revisions

En [[Teoria de la complexitat computacional|teoria de la complexitat]], la classe de complexita NEXPTIME és el conjunt dels problemes de decisió que poden ser resolts amb una [[màquina de Turing no determinista]] en espai [[Notació de Landau|O]](2^''p''(''n'')), on ''p''(''n'') és una [[Funció polinòmica|funció polinomial]] sobre ''n''.<ref>{{Ref-llibre|cognom=Michael.|nom=Sipser,|títol=Introduction to the theory of computation|url=https://www.worldcat.org/oclc/761858892|edició=3rd ed|data=2013|editorial=Cengage Learning|lloc=Boston, MA|isbn=9781133187790}}</ref><ref>{{Ref-llibre|cognom=Peter.|nom=Linz,|títol=An introduction to formal languages and automata|url=https://www.worldcat.org/oclc/669269787|edició=5th ed|data=2012|editorial=Jones & Bartlett Learning|lloc=Sudbury, MA|isbn=9781449615529}}</ref>