Word:

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].
Browse
Satire
Satiric
satirical
satirically
satirise
Satirist
Satirize
Satisdaction
Satisfaction
Satisfaction piece
Satisfaction should be made to that fund which has sustained the loss
Satisfactive
satisfactorily
satisfactoriness
Satisfactory
Satisfactory evidence
-- satisfiability problem --
Satisfiable
satisfice
satisfied
Satisfier
Satisfy
satisfying
Satisfyingly
Satius est petere fontes quam sectari rivulos
Sative
Satle
satori
Satrap
Satrapal
Satrapess
Satrapical
Satrapy
Definitions Index: # 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

About this site and copyright information - Online Dictionary Home - Privacy Policy