Stiamo lavorando per ripristinare l'app di Unionpedia nel Google Play Store
UscenteArrivo
🌟Abbiamo semplificato il nostro design per una migliore navigazione!
Instagram Facebook X LinkedIn

21 problemi NP-completi di Karp

Indice 21 problemi NP-completi di Karp

Nella teoria della complessità computazionale, i 21 problemi NP-completi di Karp sono un insieme di problemi computazionali che si presentano NP-completi.

Indice

  1. 10 relazioni: Colorazione dei grafi, Cricca (teoria dei grafi), Problema della cricca, Problema dello zaino, Problema di copertura dei vertici, Problema di copertura delle cricche, Richard Karp, Soddisfacibilità booleana, Taglio (teoria dei grafi), Taglio massimo.

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.

Vedere 21 problemi NP-completi di Karp e Colorazione dei grafi

Cricca (teoria dei grafi)

In teoria dei grafi, una cricca (o clique) è un insieme V di vertici in un grafo non orientato G, tale che, per ogni coppia di vertici in V, esiste un arco che li collega.

Vedere 21 problemi NP-completi di Karp e Cricca (teoria dei grafi)

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.

Vedere 21 problemi NP-completi di Karp e Problema della cricca

Problema dello zaino

Il problema dello zaino, o, è un problema di ottimizzazione combinatoria posto nel modo seguente.

Vedere 21 problemi NP-completi di Karp 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.

Vedere 21 problemi NP-completi di Karp e Problema di copertura dei vertici

Problema di copertura delle cricche

Nella teoria della complessità computazionale, trovare una copertura delle cricche minima è un problema NP-completo di teoria dei grafi. Il problema era uno dei 21 problemi originali di Richard Karp che erano stati dimostrati NP-completi nel suo saggio del 1972 Riducibilità tra problemi combinatori (Reducibility among Combinatorial Problems).

Vedere 21 problemi NP-completi di Karp e Problema di copertura delle cricche

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.

Vedere 21 problemi NP-completi di Karp e Richard Karp

Soddisfacibilità booleana

La soddisfacibilità booleana, o soddisfacibilità proposizionale o SAT, è il problema di determinare se una formula booleana è soddisfacibile o insoddisfacibile.

Vedere 21 problemi NP-completi di Karp e Soddisfacibilità booleana

Taglio (teoria dei grafi)

Nella teoria dei grafi, un taglio è una partizione dei vertici di un grafo in due sottoinsiemi disgiunti. Ogni taglio determina un insieme di taglio (o cut-set), definito come l'insieme degli archi che hanno i propri estremi nei due sottinsiemi della partizione.

Vedere 21 problemi NP-completi di Karp e Taglio (teoria dei grafi)

Taglio massimo

In un grafo, un taglio massimo è un taglio di dimensione almeno pari a quella di tutti gli altri tagli. Il problema della ricerca di un taglio massimo in un grafo è noto come problema max-cut.

Vedere 21 problemi NP-completi di Karp e Taglio massimo