Taula de continguts
53 les relacions: AC (Complexitat), AC0, ACC0, AM (Complexitat), APX (Complexitat), AWPP (complexitat), BQP (complexitat), CC (Complexitat), Circuit booleà, Co-NP (Complexitat), Co-NP-complet, Complexitat computacional, Complexitat de circuits, Demostració provable per probabilitat, DSPACE (Complexitat), DTIME (Complexitat), Factorització dels enters, FNP, IP (Complexitat), Jerarquia exponencial, Jerarquia polinòmica, L (complexitat), Llenguatge lliure d'estrella, Llenguatge regular, MA (Complexitat), Màquina de Turing multicinta, Màquina de Turing probabilística, Màquina oracle, NC (Complexitat), NL (Complexitat), NP (Complexitat), NP-difícil, NSPACE, NTIME (Complexitat), P (complexitat), P-complet, PolyL (Complexitat), PostBQP (Complexitat), PR (Complexitat), Problema de satisfacibilitat booleana, PSPACE-complet, QIP (Complexitat), QMA (Complexitat), RE (complexitat), RL (Complexitat), RP (Complexitat), S2P (Complexitat), SC (Complexitat), SL (Complexitat), TC0, ... Ampliar l'índex (3 més) »
AC (Complexitat)
En teoria de la complexitat, AC és una jerarquia de classes de complexitat.
Veure Classe de complexitat і AC (Complexitat)
AC0
Diagrama d'un circuit AC0. Els ''n'' bits d'entrada estan a la part de baix i la porta de la part superior genera una sola sortida. El circuit consisteix en portes AND i OR de fan-in polinòmic. La classe de complexitat AC0 és usada en complexitat de circuits.
Veure Classe de complexitat і AC0
ACC0
Diagrama d'un circuit ACC0: per un nombre fixat ''m'', el circuit consisteix en portes AND, OR i NOT i (Mod ''m''). El fan-in de cada porta està fitat per un polinomi i la profunditat del circuit per una constant. La classe de complexitat ACC0 és usada en complexitat de circuits.
Veure Classe de complexitat і ACC0
AM (Complexitat)
En teoria de la complexitat, la classe de complexitat AM (també coneguda per AM) és el conjunt dels problemes de decisió que poden ser resolts en temps polinòmic per un protocol Arthur-Merlin de dos missatges.
Veure Classe de complexitat і AM (Complexitat)
APX (Complexitat)
En teoria de la complexitat, la classe de complexitat APX és el conjunt dels problemes d'optimització a NP que tenen algorismes aproximats de temps polinòmic fitats per un factor d'aproximació que és una constat.
Veure Classe de complexitat і APX (Complexitat)
AWPP (complexitat)
En complexitat computacional, AWPP (Almost Wide Probabilistic Polynomial time) és la classe de complexitat que conté els problemes que es poden solucionar amb una màquina NP tal que per algunes funcions f computables en temps polinòmic.
Veure Classe de complexitat і AWPP (complexitat)
BQP (complexitat)
En complexitat computacional, BQP (bounded-error quantum polynomial time) és la classe de complexitat que conté els problemes de decisió que es poden resoldre amb un computador quàntic usant una quantitat de temps de computació polinòmic, amb una probabilitat d'error de com a molt 1/3 a totes les instàncies.
Veure Classe de complexitat і BQP (complexitat)
CC (Complexitat)
Una porta comparador. En teoria de la complexitat, la classe de complexitat CC (circuits comparadors, comparator circuits) és el conjunt dels problemes de decisió que poden ser resolts amb circuits comparadors de mida polinòmica.
Veure Classe de complexitat і CC (Complexitat)
Circuit booleà
En teoria de la complexitat, un circuit booleà és un model matemàtic d'un circuit digital.
Veure Classe de complexitat і Circuit booleà
Co-NP (Complexitat)
En complexitat computacional, co-NP és la classe de complexitat que conté els problemes de decisió complementaris de la classe NP.
Veure Classe de complexitat і Co-NP (Complexitat)
Co-NP-complet
En teoria de la complexitat, la classe de complexitat co-NP-complet és el conjunt dels problemes de decisió més difícils de la classe co-NP, en el sentit que son els que menys s'assemblen als de la classe P. Un problema C pertany a co-NP-complet si està a co-NP i tot problema de co-NP té una transformació polinòmica cap C.
Veure Classe de complexitat і Co-NP-complet
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.
Veure Classe de complexitat і Complexitat computacional
Complexitat de circuits
La complexitat de circuits és una branca de la teoria de la complexitat en la que les funcions booleanes es classifiquen segons la mida o profunditat del circuit booleà que la computa.
Veure Classe de complexitat і Complexitat de circuits
Demostració provable per probabilitat
En teoria de la complexitat, un sistema de demostració provable per probabilitat (o PCP per les sigles en anglès probabilistically checkable proof) és un tipus de prova que pot ser comprovada per un algorisme probabilístic usant una quantitat fitada de aleatorietat i llegint una quantitat fitada de bits de la prova.
Veure Classe de complexitat і Demostració provable per probabilitat
DSPACE (Complexitat)
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.
Veure Classe de complexitat і DSPACE (Complexitat)
DTIME (Complexitat)
En la Teoria de complexitat computacional, la família DTIME (de vegades simplement TIME) és el recurs de computació en temps de computació per una màquina de Turing determinista.
Veure Classe de complexitat і DTIME (Complexitat)
Factorització dels enters
En teoria de nombres, la factorització dels enters és el procés de trobar quins nombres primers es multipliquen per fer un nombre compost, doncs els divisors no trivials (diferent de l'1 i del mateix nombre).
Veure Classe de complexitat і Factorització dels enters
FNP
* Partit Nacional Frisó (del seu nom en frisó Fryske Nasjonale Partij), partit polític de Frísia, als Països Baixos.
Veure Classe de complexitat і FNP
IP (Complexitat)
En teoria de la complexitat, la classe de complexitat IP és el conjunt dels problemes de decisió que poden ser resolts per un sistema de demostració interactiu.
Veure Classe de complexitat і IP (Complexitat)
Jerarquia exponencial
En teoria de la complexitat, la jerarquia exponencial és una jerarquia de classes de complexitat que es l'anàloga a la jerarquia polinòmica amb temps exponencial.
Veure Classe de complexitat і Jerarquia exponencial
Jerarquia polinòmica
En teoria de la complexitat, la jerarquia polinòmica (de vegades dita jerarquia de temps polinòmic) és una jerarquia de classes de complexitat que generalitza les classes P, NP i co-NP a màquines oracle.
Veure Classe de complexitat і Jerarquia polinòmica
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 Classe de complexitat і L (complexitat)
Llenguatge lliure d'estrella
Un llenguatge regular es diu que és un llenguatge lliure d'estrella si es pot descriure amb una expressió regular construïda amb les lletres d'un alfabet, el símbol buit, tots els operadors booleans (incloent-hi complement i concatenació) però no la clausura de Kleen.
Veure Classe de complexitat і Llenguatge lliure d'estrella
Llenguatge regular
En matemàtiques, lògica i complexitat computacional un llenguatge formal és un llenguatge regular si es pot expressar usant expressions regulars.
Veure Classe de complexitat і Llenguatge regular
MA (Complexitat)
En teoria de la complexitat, la classe de complexitat MA és el conjunt dels problemes de decisió que poden ser resolts en temps polinòmic per un protocol Arthur-Merlin d'un sol missatges.
Veure Classe de complexitat і MA (Complexitat)
Màquina de Turing multicinta
Una màquina de Turing multipista és una màquina de Turing que té múltiples cintes.
Veure Classe de complexitat і Màquina de Turing multicinta
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.
Veure Classe de complexitat і Màquina de Turing probabilística
Màquina oracle
En teoria de la complexitat, una màquina oracle és màquina abstracta utilitzada per estudiar els problemes de decisió.
Veure Classe de complexitat і Màquina oracle
NC (Complexitat)
En teoria de la complexitat, la classe de complexitat NC (la Classe d'en Nick o NIck's class) és el conjunt de problemes de decisió que es poden resoldre en un temps polilogarítmic en un computador paral·lel amb un nombre polinòmic de processadors.
Veure Classe de complexitat і NC (Complexitat)
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 Classe de complexitat і 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 Classe de complexitat і NP (Complexitat)
NP-difícil
P≠NP. La part dreta és assumint que P.
Veure Classe de complexitat і NP-difícil
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 Classe de complexitat і NSPACE
NTIME (Complexitat)
En teoria de la complexitat, la classe de complexitat NTIME(f(n)) és la classe dels problemes de decisió que es poden resoldre per una màquina de Turing no determinista en un temps O(f(n)), on O és la notació de O gran, f és una funció qualsevol i n és la mida de l'entrada.
Veure Classe de complexitat і NTIME (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 Classe de complexitat і P (complexitat)
P-complet
En teoria de la complexitat, la classe de complexitat P-complet és el conjunt dels problemes de decisió que, estant a la classe P, altres problemes de P es poden reduir a ell en un temps polinòmic.
Veure Classe de complexitat і P-complet
PolyL (Complexitat)
En teoria de la complexitat, la classe de complexitat PolyL és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing determinista en un espai fitat per una funció polilogarítmica.
Veure Classe de complexitat і PolyL (Complexitat)
PostBQP (Complexitat)
En teoria de la complexitat, la classe de complexitat postBQP és el conjunt de tots els problemes que es poden solucionar amb temps polinòmic per una Màquina de Turing quàntica amb post-selecció amb un error fitat (en el sentit que l'algorisme és correcte almenys 2/3 de les vegades per totes les entrades).
Veure Classe de complexitat і PostBQP (Complexitat)
PR (Complexitat)
En teoria de la complexitat, la classe de complexitat PR és el conjunt de totes les funcions recursives primitives o, equivalentment el conjunt de tots els llenguatges formals que es poden decidir per aquestes funcions.
Veure Classe de complexitat і PR (Complexitat)
Problema de satisfacibilitat booleana
En teoria de complexitat computacional, el problema de satisfacibilitat booleana (també conegut per les sigles SAT) és el problema de determinar si existeix una interpretació que satisfà una fórmula booleana donada.
Veure Classe de complexitat і Problema de satisfacibilitat booleana
PSPACE-complet
En teoria de la complexitat, la classe de complexitat PSPACE-Complet és la classe dels problemes de decisió que es poden resoldre amb un espai de memòria polinòmic respecte la mida de l'entrada i si tot problema que es pot resoldre en espai polinòmic es pot reduir a aquest en un temps polinòmic.
Veure Classe de complexitat і PSPACE-complet
QIP (Complexitat)
En teoria de la complexitat, la classe de complexitat QIP és la classe quàntica anàloga a la classe de complexitat IP, que és el conjunt de problemes que es poden resoldre per un sistema de demostració interactiu amb un verificador de temps polinòmic i un demostrador sense restriccions.
Veure Classe de complexitat і QIP (Complexitat)
QMA (Complexitat)
En teoria de la complexitat, la classe de complexitat QMA (Quantum Merlin Authur) és el conjunt dels problemes de decisió que una resposta SI es pot verificar per un prova quàntica interactiva d'un sol missatge en un temps polinòmic.
Veure Classe de complexitat і QMA (Complexitat)
RE (complexitat)
En teoria de la complexitat, la classe de complexitat RE és la classe dels problemes de decisió on la resposta SI es pot verificar amb una màquina de Turing en un temps finit.
Veure Classe de complexitat і RE (complexitat)
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 Classe de complexitat і RL (Complexitat)
RP (Complexitat)
En teoria de la complexitat, la classe de complexitat RP (Randomized polynomial time) és el conjunt dels problemes de decisió tals que una màquina de Turing probabilística existeix amb aquestes propietats.
Veure Classe de complexitat і RP (Complexitat)
S2P (Complexitat)
En teoria de la complexitat, la classe de complexitat S és la classe de complexitat intermèdia entre el primer i segon nivell de la jerarquia polinòmica.
Veure Classe de complexitat і S2P (Complexitat)
SC (Complexitat)
En teoria de la complexitat, la classe de complexitat SC (classe de Steve, per Stephen Cook) és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing determinista en temps polinòmic (classe P) i en espai polilogarítmic (classe PolyL) O((log n)k per una constant k.
Veure Classe de complexitat і SC (Complexitat)
SL (Complexitat)
En teoria de la complexitat, la classe de complexitat SL és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing no determinista en espai log(n) tal que.
Veure Classe de complexitat і SL (Complexitat)
TC0
La classe de complexitat TC0 és usada en complexitat de circuits.
Veure Classe de complexitat і TC0
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.
Veure Classe de complexitat і Temps polinòmic
UP (Complexitat)
En teoria de complexitat, la classe de complexitat UP és la classe de problemes de decisió que es poden resoldre en temps polinòmic en una màquina de Turing no ambigua per almenys un camí que accepte per cada entrada.
Veure Classe de complexitat і UP (Complexitat)
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.
Veure Classe de complexitat і ZPP (Complexitat)