Taula de continguts
6 les relacions: Màquina de Turing no determinista, NEXPTIME, NP (Complexitat), P (complexitat), Problema de decisió, Teoria de la complexitat computacional.
Màquina de Turing no determinista
En teoria de la computació, una Màquina de Turing no determinista (MTN) és una Màquina de Turing on el seu mecanisme de control treballa com un autòmat finit no determinista.
Veure NE (Complexitat) і Màquina de Turing no determinista
NEXPTIME
En teoria de la complexitat, la classe de complexitat NEXPTIME és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing no determinista en espai O (2p(n)), on p(n) és una funció polinomial sobre n. En termes de NTIME es té També es pot definir NEXPTIME usant màquines de Turing deterministes com a verificadors.
Veure NE (Complexitat) і NEXPTIME
NP (Complexitat)
En complexitat computacional, NP és la classe de complexitat que conté els problemes de decisió que es poden resoldre amb una màquina de Turing no determinista usant una quantitat de temps de computació polinòmic, temps polinòmic.
Veure NE (Complexitat) і NP (Complexitat)
P (complexitat)
En Teoria de complexitat computacional, P és la classe de complexitat que conté els problemes de decisió que es poden resoldre amb una màquina de Turing determinista usant una quantitat de temps de computació polinòmic (temps polinòmic).
Veure NE (Complexitat) і P (complexitat)
Problema de decisió
En teoria de la computabilitat i en complexitat computacional, un problema de decisió és una qüestió en algun sistema formal amb una resposta sí o no.
Veure NE (Complexitat) і Problema de decisió
Teoria de la complexitat computacional
La teoria de la complexitat computacional se centra a classificar problemes computacionals segons el seu ús de recursos i relacionar aquestes classes entre si.
Veure NE (Complexitat) і Teoria de la complexitat computacional