Analogie tra 21 problemi NP-completi di Karp e NP-completo
21 problemi NP-completi di Karp e NP-completo hanno 13 punti in comune (in Unionpedia): Classi di complessità P e NP, Colorazione dei grafi, Complessità temporale, NP-completo, Problema della cricca, Problema dello zaino, Problema di copertura dei vertici, Richard Karp, Soddisfacibilità booleana, Stephen Cook, Teorema di Cook-Levin, Teoria dei grafi, Teoria della complessità computazionale.
Classi di complessità P e NP
Il problema delle classi P e NP è un problema tuttora aperto nella teoria della complessità computazionale. Nonostante ci sia in palio un premio di un milione di dollari il problema rimane ancora senza una soluzione (si tratta di uno dei problemi del millennio).
21 problemi NP-completi di Karp e Classi di complessità P e NP · Classi di complessità P e NP e NP-completo ·
Colorazione dei grafi
Nella teoria dei grafi, la colorazione dei grafi è un caso speciale di etichettamento dei grafi; è un'assegnazione di etichette, tradizionalmente chiamate "colori", agli elementi di un grafo soggetta a determinati vincoli.
21 problemi NP-completi di Karp e Colorazione dei grafi · Colorazione dei grafi e NP-completo ·
Complessità temporale
In informatica, la complessità temporale di un algoritmo quantifica la quantità di tempo impiegata da un algoritmo a essere eseguito in funzione della lunghezza della stringa che rappresenta l'input:226.
21 problemi NP-completi di Karp e Complessità temporale · Complessità temporale e NP-completo ·
NP-completo
Nella teoria della complessità computazionale i problemi NP-completi sono i più difficili problemi nella classe NP ("problemi risolvibili non-deterministicamente in tempo polinomiale") nel senso che, se si trovasse un algoritmo in grado di risolvere "velocemente" (nel senso di utilizzare tempo polinomiale) un qualsiasi problema NP-completo, allora si potrebbe usarlo per risolvere "velocemente" ogni problema in NP.
21 problemi NP-completi di Karp e NP-completo · NP-completo e NP-completo ·
Problema della cricca
In informatica, il problema della cricca si riferisce a uno qualsiasi dei problemi legati alla ricerca di particolari sottografi completi ("cricche") in un grafo, cioè, insiemi di elementi dove ciascuna coppia di elementi è connessa.
21 problemi NP-completi di Karp e Problema della cricca · NP-completo e Problema della cricca ·
Problema dello zaino
Il problema dello zaino, o, è un problema di ottimizzazione combinatoria posto nel modo seguente.
21 problemi NP-completi di Karp e Problema dello zaino · NP-completo e Problema dello zaino ·
Problema di copertura dei vertici
Il problema di copertura dei vertici, detto anche in inglese vertex cover, appartiene alla classe di equivalenza dei più difficili problemi risolvibili non-deterministicamente in tempo polinomiale, assieme al problema del commesso viaggiatore, il knapsack problem, ecc.
21 problemi NP-completi di Karp e Problema di copertura dei vertici · NP-completo e Problema di copertura dei vertici ·
Richard Karp
Nel 1972 ha pubblicato un elenco di 21 problemi NP-completi. Ha vinto il Premio Turing nel 1985 ed il Premio Kyōto per la tecnologia nel 2008.
21 problemi NP-completi di Karp e Richard Karp · NP-completo e Richard Karp ·
Soddisfacibilità booleana
La soddisfacibilità booleana, o soddisfacibilità proposizionale o SAT, è il problema di determinare se una formula booleana è soddisfacibile o insoddisfacibile.
21 problemi NP-completi di Karp e Soddisfacibilità booleana · NP-completo e Soddisfacibilità booleana ·
Stephen Cook
Nessuna descrizione.
21 problemi NP-completi di Karp e Stephen Cook · NP-completo e Stephen Cook ·
Teorema di Cook-Levin
Nella teoria della complessità algoritmica, il teorema di Cook-Levin, dimostrato da Stephen Cook nel suo articolo "Complessità delle Procedure di Dimostrazione dei Teoremi" ("The Complexity of Theorem Proving Procedures") del 1971, afferma che il problema di soddisfacibilità booleana è NP-completo.
21 problemi NP-completi di Karp e Teorema di Cook-Levin · NP-completo e Teorema di Cook-Levin ·
Teoria dei grafi
In matematica, informatica e, più in particolare, geometria combinatoria, la teoria dei grafi è la disciplina che si occupa dello studio dei grafi, oggetti discreti che permettono di schematizzare una grande varietà di situazioni e processi, e spesso di consentirne delle analisi in termini quantitativi e algoritmici.
21 problemi NP-completi di Karp e Teoria dei grafi · NP-completo e Teoria dei grafi ·
Teoria della complessità computazionale
La teoria della complessità computazionale è una branca della teoria della computabilità che studia le risorse minime necessarie (principalmente tempo di calcolo e memoria) per la risoluzione di un problema.
21 problemi NP-completi di Karp e Teoria della complessità computazionale · NP-completo e Teoria della complessità computazionale ·
La lista di cui sopra risponde alle seguenti domande
- In quello che appare come 21 problemi NP-completi di Karp e NP-completo
- Che cosa ha in comune 21 problemi NP-completi di Karp e NP-completo
- Analogie tra 21 problemi NP-completi di Karp e NP-completo
Confronto tra 21 problemi NP-completi di Karp e NP-completo
21 problemi NP-completi di Karp ha 21 relazioni, mentre NP-completo ha 48. Come hanno in comune 13, l'indice di Jaccard è 18.84% = 13 / (21 + 48).
Riferimenti
Questo articolo mostra la relazione tra 21 problemi NP-completi di Karp e NP-completo. Per accedere a ogni articolo dal quale è stato estratto informazioni, visitare: