NP (Complexitat) і P versus NP

Accessos directes: Diferències, Similituds, Similitud de Jaccard Coeficient, Referències.

Diferència entre NP (Complexitat) і P versus NP

NP (Complexitat) vs. P versus NP

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. Diagrama de classes de complexitat suposant que '''P''' ≠ '''NP'''. Si '''P'''.

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.

Complexitat computacional і NP (Complexitat) · Complexitat computacional і P versus NP · 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.

Màquina de Turing і NP (Complexitat) · Màquina de Turing і 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.

NP (Complexitat) і Problema de decisió · P versus NP і Problema de decisió · Veure més »

Problema del viatjant de comerç

Ruta òptima d'un viatjant de comerç passant per les quinze ciutats més grans d'Alemanya. En aquest cas s'ha considerat que el que es vol optimitzat és la distància en quilòmetres, altres opcions haurien pogut ser-lo la distància en temps, el cost econòmic dels viatges, etc. Els casos reals tenen diferents paràmetres que es volen optimitzar, no sempre compatibles entre ells, per la qual cosa cal arribar a un compromís segons el criteri de l'enginyer. El problema del viatjant de comerç és el problema d'optimització de trajectòries donat per l'enunciat següent: donat un conjunt de nodes, es tracta de trobar l'ordre de visites a seguir per tal de definir una trajectòria que passi un sol cop per a cada node i de manera que la distància total recorreguda sigui la més curta possible.

NP (Complexitat) і Problema del viatjant de comerç · P versus NP і Problema del viatjant de comerç · 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.

NP (Complexitat) і Temps polinòmic · P versus NP і Temps polinòmic · Veure més »