Taula de continguts
9 les relacions: Cambridge University Press, Màquina de Turing, Màquina de Turing no determinista, NL (Complexitat), NP (Complexitat), P (complexitat), Polinomi, PSPACE, Teoria de la complexitat computacional.
Cambridge University Press
Cambridge University Press és l'editorial de la Universitat de Cambridge, considerada la més antiga del món encara activa (va ser fundada el 1534) i sense interrupcions.
Veure Teorema de Savitch і Cambridge University Press
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 Teorema de Savitch і 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 Teorema de Savitch і Màquina de Turing no determinista
NL (Complexitat)
En teoria de la complexitat, la classe de complexitat NL és la classe dels problemes de decisió que es poden resoldre per una màquina de Turing no determinista usant una quantitat logarítmica d'espai.
Veure Teorema de Savitch і NL (Complexitat)
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 Teorema de Savitch і 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 Teorema de Savitch і P (complexitat)
Polinomi
Un polinomi és una expressió algebraica formada per la suma o resta de diversos monomis no semblants, anomenats termes del polinomi.
Veure Teorema de Savitch і Polinomi
PSPACE
En teoria de la complexitat, la classe de complexitat PSPACE és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing usant un espai polinòmic.
Veure Teorema de Savitch і PSPACE
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 Teorema de Savitch і Teoria de la complexitat computacional