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.

Usa IA

Indice

1. 7 relazioni: Classi di complessità P e NP, Logica proposizionale, NP-completo, Problema della cricca, Soddisfacibilità booleana, 2-satisfiability, 21 problemi NP-completi di Karp.

Classi di complessità P e NP

Il problema delle classi P e NP è un problema tuttora aperto nella teoria della complessità computazionale.

Vedere Teorema di Cook-Levin e Classi di complessità P e NP

Logica proposizionale

La logica proposizionale (o enunciativa) è un linguaggio formale con una semplice struttura sintattica, basata fondamentalmente su proposizioni elementari (atomi) e su connettivi logici di tipo vero-funzionale, che restituiscono il valore di verità di una proposizione in base al valore di verità delle proposizioni connesse (solitamente noti come AND, OR, NOT...).

Vedere Teorema di Cook-Levin e Logica proposizionale

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 Teorema di Cook-Levin 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.

Vedere Teorema di Cook-Levin e Problema della cricca

Soddisfacibilità booleana

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

Vedere Teorema di Cook-Levin e Soddisfacibilità booleana

2-satisfiability

2-satisfiability (o 2-SAT) è un problema di soddisfacibilità booleana con clausole composte da coppie di letterali.

Vedere Teorema di Cook-Levin e 2-satisfiability

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 Teorema di Cook-Levin e 21 problemi NP-completi di Karp

Conosciuto come Teorema di Cook.

Unionpedia è una mappa concettuale o rete semantica organizzata come un'enciclopedia o un dizionario. Esso fornisce una breve definizione di ogni concetto e le sue relazioni.

Si tratta di una mappa mentale in linea gigante che serve come base per gli schemi concettuali, immagini o sintesi sinaptica. E 'gratuito - liberi, liberi di usare e ogni elemento o documento può essere scaricato. E 'uno strumento, risorsa o di riferimento per lo studio, la ricerca, l'istruzione, la formazione o istruzione che gli insegnanti possono utilizzare, insegnanti, professori, educatori, alunni e studenti; o la scuola per il mondo accademico, a scuola, primaria, secondaria, di mezzo, università, laurea tecnica, college, università, laurea, master o dottorati; per documenti, relazioni, documenti, progetti, idee, documentazione, riassunti, sondaggi o tesi. Ecco la definizione, spiegazione, descrizione, o il significato di ogni significativo su cui avete bisogno di informazioni, e una lista o un elenco di concetti correlati come appare un glossario. Disponibile in italiano, inglese, spagnolo, portoghese, giapponese, cinese, francese, tedesco, polacco, olandese, russo, arabo, hindi, svedese, ucraino, ungherese, catalano, ceco, ebraico, danese, finlandese, indonesiano, norvegese, rumeno, turco, vietnamita, coreano, tailandese, greco, bulgaro, croato, slovacca, lituano, filippina, lettone, estone e sloveno. Altre lingue presto.

Le informazioni si basano su articoli di Wikipedia e altri progetti Wikimedia, e sono disponibili sotto la Licenza Creative Commons Attribuzione-Condividi allo stesso modo.

Unionpedia non è supportata o affiliata alla Wikimedia Foundation.

Google Play, Android e il logo di Google Play sono marchi di Google Inc.

Politica sulla riservatezza