l'accesso più veloce di browser!
25 relazioni: Algoritmo di approssimazione, Algoritmo di Davis-Putnam, Answer set programming, Clausola di Horn, Co-NP-completo, Complessità temporale, Completo (complessità), DNA, DPLL, Generazione di programmi di prova automatici, Ipotesi del tempo esponenziale, Logica proposizionale, Metodo di Quine-McCluskey, NP-completo, NP-difficile, Problema della cricca, Problema di copertura dei vertici, SAT, Scelta multipla, Sharp-P, Skolemizzazione, Teorema di Cook-Levin, Teoria della complessità computazionale, 2-satisfiability, 21 problemi NP-completi di Karp.
Algoritmo di approssimazione
Nell'informatica e nella ricerca operativa, un algoritmo di approssimazione è un algoritmo usato per trovare soluzioni approssimate a problemi di ottimizzazione.
Nuovo!!: Soddisfacibilità booleana e Algoritmo di approssimazione · Mostra di più »
Algoritmo di Davis-Putnam
L'algoritmo di Davis-Putnam fu sviluppato da Martin Davis e Hilary Putnam allo scopo di verificare la soddisfacibilità booleana di formule di logica proposizionale in forma normale congiuntiva (CNF).
Nuovo!!: Soddisfacibilità booleana e Algoritmo di Davis-Putnam · Mostra di più »
Answer set programming
Lanswer set programming (ASP) è una forma di programmazione logica di tipo dichiarativo, basata sulla semantica del modello stabile (o answer set).
Nuovo!!: Soddisfacibilità booleana e Answer set programming · Mostra di più »
Clausola di Horn
In logica, e in particolare nel calcolo proposizionale, una clausola di Horn è una disgiunzione di letterali in cui al massimo uno dei letterali è positivo.
Nuovo!!: Soddisfacibilità booleana e Clausola di Horn · Mostra di più »
Co-NP-completo
Nella teoria della complessità computazionale, i problemi computazionali che sono co-NP-completi sono i problemi più difficili in co-NP, nel senso che sono quelli che hanno le maggiori probabilità di non essere in P. Se esiste un modo di risolvere rapidamente un problema co-NP-completo, allora quell'algoritmo può essere usato per risolvere rapidamente tutti i problemi co-NP.
Nuovo!!: Soddisfacibilità booleana e Co-NP-completo · Mostra di più »
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.
Nuovo!!: Soddisfacibilità booleana e Complessità temporale · Mostra di più »
Completo (complessità)
Nella teoria della complessità computazionale, un problema computazionale è completo per una classe di complessità se è, in senso tecnico, tra i problemi "più difficili" (o "più espressivi") di quella classe.
Nuovo!!: Soddisfacibilità booleana e Completo (complessità) · Mostra di più »
DNA
L'acido desossiribonucleico o deossiribonucleico (in sigla DNA, dall'inglese DeoxyriboNucleic Acid; meno comunemente ADN, secondo la sigla italiana equivalente) è un acido nucleico che contiene le informazioni genetiche necessarie alla biosintesi di RNA e proteine, molecole indispensabili per lo sviluppo ed il corretto funzionamento della maggior parte degli organismi viventi.
Nuovo!!: Soddisfacibilità booleana e DNA · Mostra di più »
DPLL
DPLL (Davis-Putnam-Logemann-Loveland) è un algoritmo completo, basato sul backtracking, utilizzato per decidere la soddisfacibilità booleana di formule di logica proposizionale in forma normale congiuntiva (CNF), i.e. per risolvere il problema CNF-SAT.
Nuovo!!: Soddisfacibilità booleana e DPLL · Mostra di più »
Generazione di programmi di prova automatici
La generazione automatica di vettori di collaudo (ATPG) è un metodo e una tecnologia, utilizzata per trovare una sequenza di collaudo che, quando applicata ad un circuito digitale, dà la possibilità ai tester di distinguere fra il comportamento del circuito corretto e non corretto determinato da anomalie funzionali.
Nuovo!!: Soddisfacibilità booleana e Generazione di programmi di prova automatici · Mostra di più »
Ipotesi del tempo esponenziale
Nella teoria della complessità computazionale, l'ipotesi del tempo esponenziale è un'assunzione di difficoltà computazionale non dimostrata, formalizzata da, che afferma che 3-SAT (o uno qualsiasi dei vari problemi NP-completi correlati) non possono essere risolti in tempo subesponenziale nel caso peggiore.
Nuovo!!: Soddisfacibilità booleana e Ipotesi del tempo esponenziale · Mostra di più »
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...). La semantica della logica proposizionale definisce il significato dei simboli e di qualsiasi proposizione che rispetti le regole sintattiche del linguaggio, basandosi sui valori di verità associati agli atomi.
Nuovo!!: Soddisfacibilità booleana e Logica proposizionale · Mostra di più »
Metodo di Quine-McCluskey
Il metodo di Quine-McCluskey (o metodo degli implicanti primi) è un algoritmo sviluppato da Willard Van Orman Quine ed Edward McCluskey che viene utilizzato nelle reti combinatorie a due livelli di logica per la minimizzazione di una funzione booleana di n variabili.
Nuovo!!: Soddisfacibilità booleana e Metodo di Quine-McCluskey · Mostra di più »
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.
Nuovo!!: Soddisfacibilità booleana e NP-completo · Mostra di più »
NP-difficile
In teoria della complessità, i problemi NP-difficili o NP-ardui (in inglese NP-hard, da nondetermistic polynomial-time hard problem, "problema difficile non deterministico in tempo polinomiale") sono una classe di problemi che può essere definita informalmente come la classe dei problemi almeno difficili come i più difficili problemi delle classi di complessità P e NP.
Nuovo!!: Soddisfacibilità booleana e NP-difficile · Mostra di più »
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.
Nuovo!!: Soddisfacibilità booleana e Problema della cricca · Mostra di più »
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.
Nuovo!!: Soddisfacibilità booleana e Problema di copertura dei vertici · Mostra di più »
SAT
Nessuna descrizione.
Nuovo!!: Soddisfacibilità booleana e SAT · Mostra di più »
Scelta multipla
Le domande a risposta multipla sono una forma di domande di valutazione per le quali chi risponde deve selezionare una o più risposte da una lista data.
Nuovo!!: Soddisfacibilità booleana e Scelta multipla · Mostra di più »
Sharp-P
Nella teoria della complessità computazionale, la classe di complessità #P (pronunciata "sharp P" o, a volte, "numero P" o "cancelletto P") è l'insieme dei problemi di conteggio associati ai problemi decisionali nell'insieme NP.
Nuovo!!: Soddisfacibilità booleana e Sharp-P · Mostra di più »
Skolemizzazione
In logica matematica, si dice skolemizzazione l'applicazione dell'algoritmo di Skolem che trasforma un enunciato in forma normale in un enunciato universale.
Nuovo!!: Soddisfacibilità booleana e Skolemizzazione · Mostra di più »
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.
Nuovo!!: Soddisfacibilità booleana e Teorema di Cook-Levin · Mostra di più »
Teoria della complessità computazionale
In informatica, 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.
Nuovo!!: Soddisfacibilità booleana e Teoria della complessità computazionale · Mostra di più »
2-satisfiability
2-satisfiability (o 2-SAT) è un problema di soddisfacibilità booleana con clausole composte da coppie di letterali.
Nuovo!!: Soddisfacibilità booleana e 2-satisfiability · Mostra di più »
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.
Nuovo!!: Soddisfacibilità booleana e 21 problemi NP-completi di Karp · Mostra di più »
Riorienta qui:
3-SAT, 3SAT, Boolean satisfiability problem, Problema di soddisfacibilità booleana, Soddisfacibilità.
