Taula de continguts
24 les relacions: Algorisme, BPP (complexitat), BQP (complexitat), Co-NP (Complexitat), Complexitat computacional, Constant matemàtica, EXPSPACE, EXPTIME, Gramàtica lliure de context, Gramàtica regular, Gramàtica sensible al context, Llenguatge enumerable recursivament, Llenguatge recursiu, Logaritme, Màquina de Turing, Màquina de Turing no determinista, NC (Complexitat), NEXPTIME, Notació de Landau, NP (Complexitat), P (complexitat), Polinomi, Problema de decisió, PSPACE.
Algorisme
nombres primers Un algorisme (o, alternativament, algoritme) és un conjunt finit d'instruccions o passos que serveixen per a executar una tasca o resoldre un problema.
Veure Classe de complexitat і Algorisme
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.
Veure Classe de complexitat і BPP (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)
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)
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
Constant matemàtica
Una constant matemàtica és una quantitat que per definició no canvia mai el seu valor, en oposició a les variables matemàtiques.
Veure Classe de complexitat і Constant matemàtica
EXPSPACE
En teoria de la complexitat, la classe de complexita EXPSPACE és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing determinista en espai O(2p(n)), on p(n) és una funció polinomial sobre n. D'acord amb el teorema de Savitch, aquesta classe és igual a la que considera màquines de Turing no deterministes.
Veure Classe de complexitat і EXPSPACE
EXPTIME
En teoria de la complexitat, la classe de complexitat EXPTIME és el conjunt dels problemes de decisió que poden ser resolts amb una màquina de Turing determinista en temps O(2p(n)), on p(n) és una funció polinomial sobre n. En termes de DTIME es té Es coneix que i pel teorema de la jerarquia temporal: de manera que almenys una de les inclusions de la primera línia ha de ser estricta (es creu que totes ho son).
Veure Classe de complexitat і EXPTIME
Gramàtica lliure de context
En lingüística i informàtica, una gramàtica lliure de context (o de context lliure) és una gramàtica formal en la qual cada regla de producció és de la forma: On V és un símbol no terminal i w és una cadena de terminals i/o no terminals.
Veure Classe de complexitat і Gramàtica lliure de context
Gramàtica regular
En lingüística i informàtica, una gramàtica regular és una gramàtica formal en que pot ser classificada com regular-dreta o regular-esquerra.
Veure Classe de complexitat і Gramàtica regular
Gramàtica sensible al context
En lingüística i informàtica, una gramàtica sensible al context és una gramàtica formal en la qual cada regla dreta o esquerra de producció es pot embolcallar per un context de símbols terminals i no terminals.
Veure Classe de complexitat і Gramàtica sensible al context
Llenguatge enumerable recursivament
En matemàtiques, lògica i complexitat computacional un llenguatge formal és un llenguatge enumerable recursivament (o també parcialment decidible o Turing-computable) si és un subconjunt enumerable recursivament del conjunt de totes les paraules amb l'alfabet del llenguatge.
Veure Classe de complexitat і Llenguatge enumerable recursivament
Llenguatge recursiu
En matemàtiques, lògica i complexitat computacional un llenguatge formal és un llenguatge recursiu és un subconjunt recursiu del conjunt de totes les seqüències finites possibles de l'alfabet del llenguatge.
Veure Classe de complexitat і Llenguatge recursiu
Logaritme
mai l'interseca. Gràfiques de les funcions logarítmiques per a diverses bases ''b'': vermell en base ''e'', verd en base 10, i morat en base 1,7. La gràfica talla l'eix de les abscisses a ''x''.
Veure Classe de complexitat і Logaritme
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 Classe de 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 Classe de complexitat і Màquina de Turing no determinista
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)
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 Classe de complexitat і NEXPTIME
Notació de Landau
En matemàtica, la Notació de Landau, també anomenada "o minúscula" i "O majúscula", és una notació per a la comparació asimptòtica de funcions, la qual cosa permet establir la cota inferior asimptòtica, la cota superior asimptòtica i la cota ajustada asimptòtica.
Veure Classe de complexitat і Notació de Landau
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)
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)
Polinomi
Un polinomi és una expressió algebraica formada per la suma o resta de diversos monomis no semblants, anomenats termes del polinomi.
Veure Classe de complexitat і Polinomi
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 Classe de complexitat і Problema de decisió
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 Classe de complexitat і PSPACE