Indice
5 relazioni: Grafo delle implicazioni, Ipotesi del tempo esponenziale, NL (complessità), Sharp-P-completo, Soddisfacibilità booleana.
Grafo delle implicazioni
In logica matematica, un grafo delle implicazioni è un grafo orientato G(V, E) composto da un insieme di vertici V ed un insieme di archi E. Ogni vertice in V rappresenta l'assegnazione booleana di un letterale, ed ogni arco orientato da un vertice u ad un vertice v rappresenta l'implicazione materiale "Se il letterale u è vero allora lo è anche illetterale v".
Vedere 2-satisfiability e Grafo delle implicazioni
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) non possono essere risolti in tempo subesponenziale nel caso peggiore.
Vedere 2-satisfiability e Ipotesi del tempo esponenziale
NL (complessità)
La classe NL (abbreviazione di nondeterministic logarithmic space, ovvero "spazio logaritmico non deterministico", nota anche come NLOGSPACE) è una classe di complessità di problemi accettati da una macchina di Turing non deterministica in spazio logaritmico ossia con S_M(n).
Vedere 2-satisfiability e NL (complessità)
Sharp-P-completo
#P-completo (pronunciato "sharp P completo" o, talvolta, "numero P completo" o "cancelletto P completo") è una classe di complessità nella teoria della complessità computazionale.
Vedere 2-satisfiability e Sharp-P-completo
Soddisfacibilità booleana
La soddisfacibilità booleana, o soddisfacibilità proposizionale o SAT, è il problema di determinare se una formula booleana è soddisfacibile o insoddisfacibile.
Vedere 2-satisfiability e Soddisfacibilità booleana
Conosciuto come 2-SAT, 2SAT.