Vés al contingut

DSPACE (Complexitat)

De la Viquipèdia, l'enciclopèdia lliure

En teoria de la complexitat, la classe de complexitat DSPACE(f(n)) o SPACE(f(n)) és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing determinista en espai O(f(n)) i temps il·limitat. Es la contrapartida determinista de la classe NSPACE.[1][2]

Diverses classe de complexitat es defineixen en funció de DSPACE:

  • REG = DSPACE(O(1)).
  • L = DSPACE(O(log n))
  • PSPACE =
  • EXPSPACE =

Relació amb d'altres classes

[modifica]

DSPACE és la contrapart determinística de NSPACE, la classe en espai de memòria amb màquines de Turing no determinista. Pel teorema de Savitch, es te:

NTIME està relacionada amb DSPACE de la següent manera: sigui t(n) una funció construïble, es te:

Referències

[modifica]
  1. Michael., Sipser,. Introduction to the theory of computation. 3a edició. Boston, MA: Cengage Learning, 2013. ISBN 9781133187790. 
  2. Peter., Linz,. An introduction to formal languages and automata. 5th ed. Sudbury, MA: Jones & Bartlett Learning, 2012. ISBN 9781449615529.