Indice
11 relazioni: Complessità dei circuiti, Cricca (teoria dei grafi), Grafo di dischi, Grafo perfetto, Insieme indipendente (teoria dei grafi), Insieme indipendente massimale, NP-completo, Problema di copertura dei vertici, Problema di ottimizzazione, Soddisfacibilità booleana, 21 problemi NP-completi di Karp.
Complessità dei circuiti
In informatica teorica, la complessità dei circuiti è un ramo della teoria della complessità computazionale nel quale le funzioni booleane sono classificate secondo la dimensione o la profondità dei circuiti booleani che le computano.
Vedere Problema della cricca e Complessità dei circuiti
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 Problema della cricca e Cricca (teoria dei grafi)
Grafo di dischi
Una collezione di cerchi unitari e il corrispondente grafo di dischi. Nella teoria geometrica dei grafi, un grafo di dischi è il grafo d'intersezione di una famiglia di dischi unitari nel piano euclideo.
Vedere Problema della cricca e Grafo di dischi
Grafo perfetto
Nella teoria dei grafi, un grafo perfetto è un grafo nel quale il numero cromatico di ogni sottografo indotto è uguale alla dimensione della cricca più grande di quel sottografo.
Vedere Problema della cricca e Grafo perfetto
Insieme indipendente (teoria dei grafi)
Nella teoria dei grafi, un insieme indipendente o insieme stabile è un insieme di vertici in un grafo, nessuno dei quali è adiacente a due a due.
Vedere Problema della cricca e Insieme indipendente (teoria dei grafi)
Insieme indipendente massimale
Nella teoria dei grafi, un insieme indipendente massimale o insieme stabile massimale è un insieme indipendente che non è un sottoinsieme di nessun altro insieme indipendente.
Vedere Problema della cricca e Insieme indipendente massimale
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.
Vedere Problema della cricca e NP-completo
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 Problema della cricca e Problema di copertura dei vertici
Problema di ottimizzazione
In matematica e in informatica, un problema di ottimizzazione è il problema di trovare la migliore soluzione fra tutte le soluzioni fattibili.
Vedere Problema della cricca e Problema di ottimizzazione
Soddisfacibilità booleana
La soddisfacibilità booleana, o soddisfacibilità proposizionale o SAT, è il problema di determinare se una formula booleana è soddisfacibile o insoddisfacibile.
Vedere Problema della cricca e Soddisfacibilità booleana
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.
Vedere Problema della cricca e 21 problemi NP-completi di Karp
Conosciuto come Problema della cricca massima.