satisfiability problem

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].
Mentioned in ?
References in periodicals archive ?
For checking rules for inconsistency it is proposed to use AND/OR-graph and solution of satisfiability problem for Boolean formulas (SATisfiability problem--SAT) [11].
A special planar satisfiability problem and a consequence of its NP-completeness.
In this paper, we will call as 'WSPS' (Workflow Satisfiability Problem situation) a situation where the WFMS is unable to find (for availability or security reasons) an authorized user to assign to the current task instance in a workflow instance.
4 SATISFIABILITY AND THE MAXIMUM SATISFIABILITY PROBLEM (SAT/MAX-SAT)
The papers have been organized into sections on architecture description languages, applications related to the Boolean satisfiability problem, debug and diagnosis, high level test and automatic test- pattern generators, validation, and advances in verification methodology for complex designs.
To demonstrate the feasibility of parasitic computing, Barabasi and his collaborators chose a mathematical question known as the satisfiability problem (SN: 5/6/00, p.
3 we need to understand the satisfiability problem for inequalities over the lattice DM(H).
We first present an approximation preserving reduction from this satisfiability problem to R|[r.
The fundamental satisfiability problem for word equations has been solved recently by Makanin.
This work is focussed on the development and analysis of a new class of algorithms, called cellular memetic algorithms cMAs), which will be evaluated here on the satisfiability problem (SAT).
For full clauses we obtain a similar result by reduction to the satisfiability problem for O(f[(m).
The problem we tackle here extends the satisfiability problem for set unification, shown to be NP-complete in Kapur and Narendran [1992].