Taula de continguts
11 les relacions: AC (Complexitat), Classe de complexitat, L (complexitat), Màquina de Turing, Màquina de Turing no determinista, NSPACE, P (complexitat), Problema de decisió, RL (Complexitat), Teorema de Savitch, Teoria de la complexitat computacional.
AC (Complexitat)
En teoria de la complexitat, AC és una jerarquia de classes de complexitat.
Veure NL (Complexitat) і AC (Complexitat)
Classe de complexitat
En teoria de complexitat, una classe de complexitat és un conjunt de problemes de decisió de complexitat relacionada.
Veure NL (Complexitat) і Classe de complexitat
L (complexitat)
En teoria de la complexitat, la classe de complexitat L, també coneguda com a LSPACE o DLOGSPACE, és la classe dels problemes de decisió que es poden resoldre per una màquina de Turing determinista usant una quantitat logarítmica d'espai.
Veure NL (Complexitat) і L (complexitat)
Màquina de Turing
Fotografia d'Alan Turing (1930) La màquina de Turing és un model computacional introduït per Alan Turing en el treball "On computable numbers, with an application to the Entscheidungsproblem", publicat per la Societat Matemàtica de Londres, en el qual s'estudiava la qüestió plantejada per David Hilbert sobre si les matemàtiques són decidibles, és a dir, si hi ha un mètode definit que pugui aplicar-se a qualsevol sentència matemàtica i que resolgui si és certa o no.
Veure NL (Complexitat) і Màquina de Turing
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 NL (Complexitat) і Màquina de Turing no determinista
NSPACE
En teoria de la complexitat, la classe de complexitat NSPACE(f(n)) és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing no determinista en espai O(f(n)) i temps il·limitat.
Veure NL (Complexitat) і NSPACE
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 NL (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 NL (Complexitat) і Problema de decisió
RL (Complexitat)
En teoria de la complexitat, la classe de complexitat RL (també coneguda per RLP) és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing probabilística en espai logarítmic i temps polinòmic.
Veure NL (Complexitat) і RL (Complexitat)
Teorema de Savitch
En teoria de la complexitat, el Teoremoa de Savitch, provat per Walter Savitch el 1970 dona la relació entre complexitats espacials deterministes i no deterministes.
Veure NL (Complexitat) і Teorema de Savitch
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 NL (Complexitat) і Teoria de la complexitat computacional