Indice
10 relazioni: Algebra di Boole, Architettura dei calcolatori, Classi di complessità P e NP, Complessità temporale, Forma normale congiuntiva, Macchina di Turing, Problema decisionale, Soddisfacibilità booleana, Teoria della complessità algoritmica, Turing equivalenza.
- Teoremi nella teoria della complessità computazionale
Algebra di Boole
Lalgebra di Boole (anche detta algebra booleana, logica booleana o reticolo booleano), in matematica e logica matematica, è il ramo dell'algebra in cui le variabili possono assumere solamente i valori vero e falso (valori di verità), generalmente denotati rispettivamente come 1 e 0.
Vedere Teorema di Cook-Levin e Algebra di Boole
Architettura dei calcolatori
Larchitettura dei calcolatori, nell'informatica, elettronica o più in generale dei sistemi elettronici digitali, è la maniera in cui sono collegati tra loro i componenti hardware elementari di un sistema di elaborazione.
Vedere Teorema di Cook-Levin e Architettura dei calcolatori
Classi di complessità P e NP
Il problema delle classi P e NP è un problema tuttora aperto nella teoria della complessità computazionale. Nonostante ci sia in palio un premio di un milione di dollari il problema rimane ancora senza una soluzione (si tratta di uno dei problemi del millennio).
Vedere Teorema di Cook-Levin e Classi di complessità P e NP
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.
Vedere Teorema di Cook-Levin e Complessità temporale
Forma normale congiuntiva
Nella logica booleana, una formula è in forma normale congiuntiva o congiunta (FNC), indicata anche come CNF (acronimo di Conjunctive Normal Form) se è una congiunzione di clausole, dove le clausole sono una disgiunzione di letterali.
Vedere Teorema di Cook-Levin e Forma normale congiuntiva
Macchina di Turing
In informatica, una macchina di Turing (o più brevemente MdT) è una macchina ideale che manipola i dati contenuti su un nastro di lunghezza potenzialmente infinita, secondo un insieme prefissato di regole ben definite.
Vedere Teorema di Cook-Levin e Macchina di Turing
Problema decisionale
Un problema decisionale nell'ambito della matematica riguarda un problema di scelta in cui si deve prendere una decisione tra un elevato numero di soluzioni (ammissibili) alternative, sulla base di uno o più criteri.
Vedere Teorema di Cook-Levin e Problema decisionale
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
Teoria della complessità algoritmica
La teoria della complessità algoritmica o teoria algoritmica della complessità si occupa dello studio della complessità descrittiva degli algoritmi e non delle risorse computazionali (memoria occupata e tempo di calcolo) necessarie ad eseguirli.
Vedere Teorema di Cook-Levin e Teoria della complessità algoritmica
Turing equivalenza
La Turing equivalenza è la proprietà dei modelli di calcolo che hanno lo stesso potere computazionale di una macchina di Turing universale (MdTu).
Vedere Teorema di Cook-Levin e Turing equivalenza
Vedi anche
Teoremi nella teoria della complessità computazionale
- Teorema dell'esperto
- Teorema dello speedup
- Teorema dello speedup di Blum
- Teorema di Böhm-Jacopini
- Teorema di Cook-Levin
- Teorema di Savitch
Conosciuto come Teorema di Cook.