Similituds entre NP (Complexitat) і NP-complet
NP (Complexitat) і NP-complet tenen 6 coses en comú (en Uniopèdia): Complexitat computacional, Isomorfisme de grafs, Màquina de Turing no determinista, Problema de satisfacibilitat booleana, Problema del viatjant de comerç, Temps polinòmic.
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 і NP-complet ·
Isomorfisme de grafs
En teoria de grafs, un isomorfisme de graf és una funció f bijectiva entre els vèrtexs de dos grafs G i H. amb la propietat de què qualsevol dos vèrtex u i v de G són adjacents si i només si f(u) i f(v) són adjacents en H. Si es pot construir un isomorfisme entre dos grafs, llavors diem que aquests dos grafs són isomòrfics.
Isomorfisme de grafs і NP (Complexitat) · Isomorfisme de grafs і NP-complet ·
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.
Màquina de Turing no determinista і NP (Complexitat) · Màquina de Turing no determinista і NP-complet ·
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.
NP (Complexitat) і Problema de satisfacibilitat booleana · NP-complet і Problema de satisfacibilitat booleana ·
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ç · NP-complet і Problema del viatjant de comerç ·
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 · NP-complet і Temps polinòmic ·
La llista anterior respon a les següents preguntes
- En què s'assemblen NP (Complexitat) і NP-complet
- Què tenen en comú NP (Complexitat) і NP-complet
- Semblances entre NP (Complexitat) і NP-complet
Comparació entre NP (Complexitat) і NP-complet
NP (Complexitat) té 11 relacions, mentre que NP-complet té 10. Com que tenen en comú 6, l'índex de Jaccard és 28.57% = 6 / (11 + 10).
Referències
En aquest article es mostra la relació entre NP (Complexitat) і NP-complet. Per accedir a cada article de la qual es va extreure la informació, si us plau visiteu: