Accés més ràpid que el navegador!
21 les relacions: Aparellament (teoria de grafs), BPP (complexitat), Cambridge University Press, Circuit booleà, Classe de complexitat, Complexitat computacional, Connectivitat-st, EXPTIME, L (complexitat), Màquina de Turing, Màxim comú divisor, Nombre primer, NP (Complexitat), P versus NP, P-complet, Problema de decisió, Programació lineal, PSPACE, RP (Complexitat), Si i només si, Temps polinòmic.
Aparellament (teoria de grafs)
Un aparellament d'un graf, representat en vermell En la disciplina matemàtica de la teoria de grafs, un aparellament d'un graf és un conjunt d'arestes sense vèrtexs en comú.
Nou!!: P (complexitat) і Aparellament (teoria de grafs) · Veure més »
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!!: P (complexitat) і BPP (complexitat) · Veure més »
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.
Nou!!: P (complexitat) і Cambridge University Press · Veure més »
Circuit booleà
En teoria de la complexitat, un circuit booleà és un model matemàtic d'un circuit digital.
Nou!!: P (complexitat) і Circuit booleà · 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!!: P (complexitat) і Classe de 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!!: P (complexitat) і Complexitat computacional · Veure més »
Connectivitat-st
En teoria de la complexitat, el problema de connectivitat-st o STCON (pel nom en anglès st-connectivity) és un problema de decisió tal que donat un graf dirigit, cal saber si un vèrtex t és accessible des de s. Formalment, el problema es descriu així:CAMÍ.
Nou!!: P (complexitat) і Connectivitat-st · Veure més »
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).
Nou!!: P (complexitat) і EXPTIME · Veure més »
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.
Nou!!: P (complexitat) і L (complexitat) · 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!!: P (complexitat) і Màquina de Turing · Veure més »
Màxim comú divisor
El màxim comú divisor (mcd) de dos o més nombres enters és, a excepció del signe, el major divisor possible de tots ells.
Nou!!: P (complexitat) і Màxim comú divisor · Veure més »
Nombre primer
Un nombre primer és un nombre enter superior a 1 que admet exactament dos divisors: 1 i ell mateix.
Nou!!: P (complexitat) і Nombre primer · 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!!: P (complexitat) і NP (Complexitat) · Veure més »
P versus NP
Diagrama de classes de complexitat suposant que '''P''' ≠ '''NP'''. Si '''P'''.
Nou!!: P (complexitat) і P versus NP · Veure més »
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.
Nou!!: P (complexitat) і P-complet · 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!!: P (complexitat) і Problema de decisió · Veure més »
Programació lineal
Representació pictòrica d'un programa lineal simple de dues variables i sis desigualtats. El conjunt de solucions factibles es mostra en vermell clar i conforma un polítop bidimensional. La funció lineal de cost està representada per una línia vermella i una fletxa: la línia vermella és el conjunt de nivell de la funció de cost, i la fletxa indica la direcció en la qual s'està optimitzant. La programació lineal (PL) és un mètode matemàtic per determinar una manera d'aconseguir el millor resultat (com, per exemple, el benefici màxim o el cost mínim) d'un cert model matemàtic donats una sèrie de requisits (restriccions) representats com relacions lineals.
Nou!!: P (complexitat) і Programació lineal · Veure més »
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.
Nou!!: P (complexitat) і PSPACE · Veure més »
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.
Nou!!: P (complexitat) і RP (Complexitat) · Veure més »
Si i només si
Símbols lògicsper a representarsii.
Nou!!: P (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!!: P (complexitat) і Temps polinòmic · Veure més »
