0

Question 1: SAT is defined as a language of all satisfiable boolean formulas. Does definition of SAT imply that all 2-SAT instances are instances of SAT? If 2-SAT is an instance of SAT, why is it not NP-complete?

Question 2: Chapter 6 (Boolean circuits) of Computational complexity by Arora and Barak. Every Boolean function can be expressed by a Boolean formula. SAT is defined as a language of all satisfiable boolean formulas. By Shannon's Theorem, for every $n$>1, there exists a function f: {0,1}$^n$ $\rightarrow$ {0,1} that cannot be computed by a circuit $C$ of size 2$^n$/(10$n$). Why does not Shannon's Theorem imply that there are SAT formulas that are not computable by polynomial size circuits?

istex
  • 11

1 Answers1

1

Question 1: Yes, 1SAT and 2SAT (satisfability of boolean formulas in CNF with at most 1 or 2 literals per clause) are special cases of SAT (satisfability of boolean formulas). But they are easy: 1SAT is trivial (if both a variable and it's negation appear, non satisfiable; else satisfiable), 2SAT can be solved in linear time too by Krom's algorithm. But the general case is hard, in fact NP-complete.

vonbrand
  • 27,812
  • SAT is NP-complete because instances of every NP language can be Karp reduced to instances of SAT. Since instances of 2-SAT are instances of SAT, instances of any NP language are Karp reducible to 2-SAT as well. So, 2-SAT should be NP-complete. Why is it not the case? – istex Mar 22 '20 at 10:37
  • 1
    got it: since Karp reduction from A to B is not a bijection between languages A and B, instances of any NP language are not necessarily mapped to a unique and every SAT instance. It has not been shown that any instance of any NP languaged can be mapped to a 2-SAT instance by Karp reduction. – istex Mar 22 '20 at 20:32