From Wikipedia, the free encyclopedia
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:
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:
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.