Accés més ràpid que el navegador!
13 les relacions: BPP (complexitat), Classe de complexitat, Co-NP (Complexitat), Complexitat computacional, Màquina de Turing, Màquina de Turing probabilística, NP (Complexitat), P (complexitat), P versus NP, Problema de decisió, Si i només si, Temps polinòmic, ZPP (Complexitat).
BPP (complexitat)
En teoria de la complexitat, la classe de complexitat BPP (bounded-error probabilistic polynomial time) és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing probabilística en un temps polinòmic amb un error fitat de 1/2 per totes les instàncies.
Nou!!: RP (Complexitat) і BPP (complexitat) · Veure més »
Classe de complexitat
En teoria de complexitat, una classe de complexitat és un conjunt de problemes de decisió de complexitat relacionada.
Nou!!: RP (Complexitat) і Classe de complexitat · Veure més »
Co-NP (Complexitat)
En complexitat computacional, co-NP és la classe de complexitat que conté els problemes de decisió complementaris de la classe NP.
Nou!!: RP (Complexitat) і Co-NP (Complexitat) · Veure més »
Complexitat computacional
La teoria de complexitat computacional és la part de la teoria de la computabilitat que estudia els recursos requerits durant el càlcul per resoldre un problema.
Nou!!: RP (Complexitat) і Complexitat computacional · Veure més »
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.
Nou!!: RP (Complexitat) і Màquina de Turing · Veure més »
Màquina de Turing probabilística
En teoria de la complexitat, s'utilitzen Màquines de Turing probabilística per definir diferents classes de complexitat.
Nou!!: RP (Complexitat) і Màquina de Turing probabilística · Veure més »
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.
Nou!!: RP (Complexitat) і NP (Complexitat) · Veure més »
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).
Nou!!: RP (Complexitat) і P (complexitat) · Veure més »
P versus NP
Diagrama de classes de complexitat suposant que '''P''' ≠ '''NP'''. Si '''P'''.
Nou!!: RP (Complexitat) і P versus NP · Veure més »
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.
Nou!!: RP (Complexitat) і Problema de decisió · Veure més »
Si i només si
Símbols lògicsper a representarsii.
Nou!!: RP (Complexitat) і Si i només si · Veure més »
Temps polinòmic
En teoria de complexitat, temps polinòmic es refereix al temps de computació d'un problema on el temps, m(n), no és major que una funció polinòmica de la mida del problema, n. Donada qualsevol màquina abstracta tindrà una classe de complexitat corresponent als problemes que es poden resoldre en temps polinòmic en dita màquina.
Nou!!: RP (Complexitat) і Temps polinòmic · Veure més »
ZPP (Complexitat)
En teoria de la complexitat, la classe de complexitat ZPP (zero error probabilistic polynomial time) és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing probabilística tal que.
