Home Articles FAQs XREF Games Software Instant Books BBS About FOLDOC RFCs Feedback Sitemap

satisfiability problem

You are here: irt.org | FOLDOC | satisfiability problem

A problem used as an example in complexity theory. It can be stated thus:

 Given a Boolean expression E, decide if there is some
 assignment to the variables in E such that E is true.

A Boolean expression is composed of Boolean variables, (logical) negation (NOT), (logical) conjunction (AND) and parentheses for grouping. The satisfiability problem was the first problem to be proved to be NP-complete (by Cook).

["Introduction to Automata Theory, Languages, and Computation" by Hopcroft and Ullman, pub. Addison-Wesley].


Nearby terms: SATAN « Sather « Sather-K « satisfiability problem » saturation » Saturday-night special » sausage code

FOLDOC, Topics, A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, ?, ALL

©2018 Martin Webb