Velocity Moments: Difference between revisions
Jump to navigation
Jump to search
en>Murraysettle m moved User:Murraysettle to Velocity Moments: This page is about velocity moments. |
en>Magioladitis m →External links: Remove unicode control characters (CHECKWIKI error 16) using AWB (9369) |
||
| Line 1: | Line 1: | ||
In theoretical computer science, the '''circuit satisfiability problem''' (also known as '''CIRCUIT-SAT''', '''CircuitSAT''', '''CSAT''', etc.) is the [[decision problem]] of determining whether a given [[Boolean circuit]] has an assignment of its inputs that makes the output true.<ref name="np-complete-problems">{{cite web|url=http://people.clarkson.edu/~alexis/PCMI/Notes/lectureB07.pdf|title=Lecture 7: NP-Complete Problems|date=July 5, 2000|author=David Mix Barrington and Alexis Maciel}}</ref> | |||
CircuitSAT has been proven to be [[NP-complete]].<ref>{{cite web|url=http://www.cs.berkeley.edu/~luca/cs170/notes/lecture22.pdf|title=Notes for Lecture 23: NP-completeness of Circuit-SAT|author=Luca Trevisan|date=November 29, 2001}}</ref> In fact, it is a prototypical NP-complete problem; the [[Cook–Levin theorem]] is sometimes proved on CircuitSAT instead of on [[Boolean satisfiability problem|SAT for Boolean expressions]] and then reduced to the other satisfiability problems to prove their NP-completeness.<ref name="np-complete-problems" /><ref>See also, for example, the informal proof given in [[Scott Aaronson]]'s [http://www.scottaaronson.com/democritus/lec6.html lecture notes] from his course ''Quantum Computing Since Democritus''.</ref> | |||
There is a straightforward reduction from CircuitSAT with 2-input NAND gates (a [[Functional completeness|functionally-complete]] set of Boolean operators) to [[Satisfiability Problem|SAT]]: assign every [[Netlist|net]] in the circuit a variable, then replace every NAND gate with inputs ''v<sub>1</sub>'' and ''v<sub>2</sub>'' and output ''v<sub>3</sub>'' with the [[conjunctive normal form]] clauses (''v<sub>1</sub>'' ∨ ''v<sub>3</sub>'') ∧ (''v<sub>2</sub>'' ∨ ''v<sub>3</sub>'') ∧ (¬''v<sub>1</sub>'' ∨ ¬''v<sub>2</sub>'' ∨ ¬''v<sub>3</sub>''). These clauses completely describe the relationship between the three variables. Adding an additional clause constraining the circuit's output variable to be true completes the reduction; an assignment of the variables satisfying all of the constraints exists if and only if the original circuit is satisfiable, and any solution is a solution of the original problem.<ref name="np-complete-problems" /><ref>{{cite web|url=http://reference.kfupm.edu.sa/content/a/l/algorithms_for_satisfiability_in_combina_410353.pdf|title=Algorithms for Satisfiability in Combinational Circuits Based on Backtrack Search and Recursive Learning|author=Marques-Silva, João P. and Luís Guerra e Silva|year=1999}}</ref> (The converse, that SAT is reducible to CircuitSAT, is even easier—we simply rewrite the Boolean formula as a circuit and solve that.) | |||
The satisfiability of a circuit containing m arbitrary binary gates can be decided in time <math>O(2^{0.4058m})</math>.<ref>{{cite web|url=http://www.pdmi.ras.ru/preprint/2009/09-10.html|title=An O(2^{0.4058m}) upper bound for Circuit SAT|author=Sergey Nurk|date=December 1, 2009}}</ref> | |||
== References == | |||
{{reflist}} | |||
== See also == | |||
* [[Satisfiability problem]] | |||
[[Category:NP-complete problems]] | |||
[[Category:Computational problems]] | |||
[[Category:Computability theory]] | |||
{{comp-sci-theory-stub}} | |||
Revision as of 17:59, 23 July 2013
In theoretical computer science, the circuit satisfiability problem (also known as CIRCUIT-SAT, CircuitSAT, CSAT, etc.) is the decision problem of determining whether a given Boolean circuit has an assignment of its inputs that makes the output true.[1]
CircuitSAT has been proven to be NP-complete.[2] In fact, it is a prototypical NP-complete problem; the Cook–Levin theorem is sometimes proved on CircuitSAT instead of on SAT for Boolean expressions and then reduced to the other satisfiability problems to prove their NP-completeness.[1][3]
There is a straightforward reduction from CircuitSAT with 2-input NAND gates (a functionally-complete set of Boolean operators) to SAT: assign every net in the circuit a variable, then replace every NAND gate with inputs v1 and v2 and output v3 with the conjunctive normal form clauses (v1 ∨ v3) ∧ (v2 ∨ v3) ∧ (¬v1 ∨ ¬v2 ∨ ¬v3). These clauses completely describe the relationship between the three variables. Adding an additional clause constraining the circuit's output variable to be true completes the reduction; an assignment of the variables satisfying all of the constraints exists if and only if the original circuit is satisfiable, and any solution is a solution of the original problem.[1][4] (The converse, that SAT is reducible to CircuitSAT, is even easier—we simply rewrite the Boolean formula as a circuit and solve that.)
The satisfiability of a circuit containing m arbitrary binary gates can be decided in time .[5]
References
43 year old Petroleum Engineer Harry from Deep River, usually spends time with hobbies and interests like renting movies, property developers in singapore new condominium and vehicle racing. Constantly enjoys going to destinations like Camino Real de Tierra Adentro.
See also
- ↑ 1.0 1.1 1.2 Template:Cite web
- ↑ Template:Cite web
- ↑ See also, for example, the informal proof given in Scott Aaronson's lecture notes from his course Quantum Computing Since Democritus.
- ↑ Template:Cite web
- ↑ Template:Cite web