Boolean satisfiability problem
The Boolean satisfiability problem is a kind of problem in math-based logic. In propositional logic, a formula is satisfiable if the variables it uses can be gi…
The Boolean satisfiability problem is a kind of problem in math-based logic. In propositional logic, a formula is satisfiable if the variables it uses can be given values so that it becomes true. If however for a given formula, no values exist so that the formula becomes true and the formula will always be false no matter what values its variables have it is called "unsatisfiable".
This problem is also known as Boolean or propositional satisfiability. Computer scientists usually call it SAT. Complexity theory believes that the formula should be in a special form, known as conjunctive normal form. A formula that is in this form has clauses. Clauses are joined by a "logical and". Each clause has several literals. They are joined by a "logical or". A literal and its complement cannot appear in the same clause. The problem may also have other names. The names depend on what the logical formula looks like. The names also depend on how many variables are used per clause.
A formula that satisfies 3SAT looks like the following:
- (A1 OR B1 OR C1) AND
- (A2 OR B2 OR C2) AND
- (A3 OR B3 OR C3) AND ...
In this case (A1 OR B1 OR C1) is an example for a clause, and B1 is one of the literals of this clause.
At the beginning of the 1970s, Stephen Cook and Leonid Levin showed that the problem is NP-complete. This is known as the Cook–Levin theorem.
The problem 3SAT uses three variables per clause. It is one of the 21 NP-complete problems. They were defined by Richard Karp in 1972.
Content Disclaimer
Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.
- The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
- There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
- It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
- Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
- Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.