Indice
10 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, 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 non deterministici 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 problemi completi non deterministici, 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
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.