3SAT - Another 3SAT to 2SAT Conversion
reas...@gmail.com
(a+b+c)(~a+~b+~c)(a+~c+d)(~b+~d+e)
(~b+c+~d)(c+d+e)(~a+~c+~e)
Choose any two literals from a 3-clause
and form a 2-clause. Do this for each
3-clause.
For example, choose the two lowest order
literals from each 3-clause:
(a+b)(~a+~b)(a+~c)(~b+~d)
(~b+c)(c+d)(~a+~c)
Any satisfying assignment for this 2SAT expression
is also a satisfying assignment for the original
3SAT expression.
a~b~cd is a satisfying assignment for both
the 2SAT and the 3SAT instance:
(A+b)(~a+~B)(A+~C)(~B+~d)
(~B+c)(c+D)(~a+~C)
(A+b+c)(~a+~B+~C)(A+~C+D)(~B+~d+e)
(~B+c+~d)(c+D+e)(~a+~C+~e)
For any satisfying assignment of the original
3SAT instance there exists (many) 2SAT instances
that are satisfied with the same assignment.
Now for the 3SAT to 2SAT conversion.
For any 3SAT instance there exists a set
of 2SAT instances such that any satisfying
assignment of a 2SAT instance in the set is
also a satisfying assignment of the 3SAT
instance and any satisfying assignment of
the 3SAT instance is also a satisfying
assignment of at least one of the 2SAT instances.
Consider the 3SAT instance (a+b+c).
There are three possible 2-clauses
I can create: (a+b), (a+c), or (b+c).
I only need two 2SAT instances to make my set.
(a+b) and (a+c) are two instances I can use.
Any satisfying assignment of either 2SAT
expression is also a solution to (a+b+c).
Any satisfying assignment of (a+b+c) is
also a satisfying assignment of either
(a+b) or (a+c) (or both).
I haven't been able to determine if the
minimum number of 2SAT instances required
for the set is super polynomial.
This seems related to MaxSAT.
Is there literature on "simulating" 3SAT with 2SAT?
Russell
- 2 many 2 count
Jan
Hi
Try something "simpler" like defining a "two input AND gate" in
2SAT...
Regards, Jan
reas...@gmail.com
(a+b)(~a+b)(a+~b)
Jan
Ok, I'll rephrase, "two input AND gate" with one output variable ie.
like this 3SAT expression: (a+~f)(b+~f)(~a+~b+f)
Regards, Jan
reas...@gmail.com
Choose the two lowest order literals in each clause:
(a+~f)(b+~f)(~a+~b)
~a~f is a satisfying assignment.
I can "emulate" this 2+SAT expression
(a+~f)(b+~f)(~a+~b+f)
with two 2SAT instances:
1st 2SAT: (a+~f)(b+~f)(~a+~b)
2nd 2SAT: (a+~f)(b+~f)(~a+f)
Every satisfying assignment of any of these 2SAT instances
is also a solution for the 3SAT instance and any
satisfying assignment of the 3SAT instance
is also a solution of at least one of the 2SAT instances.
I only need the 2nd 2SAT expression to handle the
case where a,b, and f are all true.
(a+~f)(b+~f)(~a+~b) contains every solution to
(a+~f)(b+~f)(~a+~b+f) except when all variables are true.
I also found a new (to me) reduction.
Is there a name for this reduction?
(a+b+x)(a+b+y)(a+b+z)(~x+~y+~z) = (a+b)
Patricia Shanahan
...
> For any 3SAT instance there exists a set
> of 2SAT instances such that any satisfying
> assignment of a 2SAT instance in the set is
> also a satisfying assignment of the 3SAT
> instance and any satisfying assignment of
> the 3SAT instance is also a satisfying
> assignment of at least one of the 2SAT instances.
>
> Consider the 3SAT instance (a+b+c).
> There are three possible 2-clauses
> I can create: (a+b), (a+c), or (b+c).
> I only need two 2SAT instances to make my set.
>
> (a+b) and (a+c) are two instances I can use.
> Any satisfying assignment of either 2SAT
> expression is also a solution to (a+b+c).
> Any satisfying assignment of (a+b+c) is
> also a satisfying assignment of either
> (a+b) or (a+c) (or both).
>
> I haven't been able to determine if the
> minimum number of 2SAT instances required
> for the set is super polynomial.
Unless there is something clever going on that you have not described,
the number of clauses in the 2SAT instance is 2^m, where m is the number
of clauses in the 3SAT that have three distinct terms.
I am going to use "3clause" to mean "3CNF clause with three distinct terms".
Let f(n) be the number of 2SAT instances for a 3CNF expression with m
3clauses. Suppose, in converting a 3SAT, you have processed m 3clauses,
have f(m) 2SAT instances, and see another 3clause. It generates two
alternative 2SAT clauses. For each of the f(m) existing instances, you
need two new instances formed by appending each of the new clauses to
it. Thus f(m+1) is 2*f(m). f(1) is 2 - a single 3clause results in two
2SAT instances. f(n) is 2^n.
The number of 3 clauses can be linear in the length of the 3SAT
instance, so the number of 2SAT instances can increase exponentially
with the input length.
Exponential growth is, of course, normal, unsurprising behavior for a
reduction from an NPC problem to a known P problem.
Patricia
Jan
The "cut" is to use a single formula... besides that: a,b=true does't
make 1st 2SAT true and there must be a typo in the 2nd 2SAT
expression.
Regards, Jan
Martin Musatov
> Man-I-Fold:=MartinMichaelMusatov L in math bf NP. Proof 6NP=P.~~~~\
sSupplementary Material 1 Encoding 3-SAT problem using TCP checksum ...
(greater than zero) of 3-SAT clauses is combined with 2-SAT clauses,
is NP-complete. To illustrate the use of these operators, consider the
following ...http://www.nd.edu/~parasite/sup.pdf - - Cached - Similar
pagesA New Bound for an NP-Hard Subclass of 3-SAT Using Backdoors-CNF
as a subclass of 3-Sat ∈ NP directly implies ..... solve a 2-Sat
instance for each possible truth assignment of the variables in
B ...http://www.springerlink.com/index/v82v617444665h87.pdf - Similar
pagesDiscrete Applied Mathematics : Computational complexity of
some ...On the other hand, it is NP-hard to decide the satisfiability
of 3-SAT instances in which ... It is well known that 2-SAT can be
solved in polynomial time, while Cook [4] .... We shall prove Theorem
2 by reduction from another problem. ...http://linkinghub.elsevier.com/
retrieve/pii/S0166218X06004677 - Similar pages3sat 3sat Is NP-Complete
Another Variant of 3sat The Proof (concluded)c 2004 Prof. Yuh-Dauh
Lyuu, National Taiwan University. Page 259. Another Variant of 3sat.
Proposition 32 3sat is NP-complete for expressions in ...http://
www.csie.ntu.edu.tw/~lyuu/complexity/2004/c_20041027.pdf - - Cached -
Similar pagesSolving 3-Sat Problem - ISU Complex Computation Lab13 Jun
2008 ... This example is similar to 2-SAT example, except that the
predicate used in this example is a 3-SAT with 4 variables and 6
clauses. ...http://www.complex.iastate.edu/download/Trend/examples/
3SAT.html - 12k - Cached - Similar pagesThe Phase Transition in 1-in-k
SAT and NAE 3-SATtion [2], while the backbone of random 3-SAT exhibits
a "first-order" (discontinuous) phase ... 1-in-k SAT is NP-complete,
while 2-SAT is solvable ...http://users.soe.ucsc.edu/~optas/papers/
1ink.pdf - - Cached - Similar pagesApproximation Hardness of Short
Symmetric Instances of MAX-3SATsymmetric MAX-3SAT for which the
approximation gap property is still NP-hard ..... implications|with a
similar variable of another gadget. ...http://www.maths.ox.ac.uk/rand-
apx/eccc-bal-3SAT.ps - - Cached - Similar pagesDid you mean to search
for: 3SAT - Another 3SAT to 2 SAT NP12345678910Next
-------------------------------
[P=NP, only a fool would insist on the impossibility of something that
could bring so much good in the world. --Martin Musatov]
reas...@gmail.com
> reaste...@gmail.com wrote:
> > I haven't been able to determine if the
> > minimum number of 2SAT instances required
> > for the set is super polynomial.
>
> Unless there is something clever going on that you have not described,
> the number of clauses in the 2SAT instance is 2^m, where m is the number
> of clauses in the 3SAT that have three distinct terms.
No single 2SAT instance can have more than O(N^2) distinct clauses.
You are correct that the number of different 2SAT instances
I can create by choosing two literals from each 3-clause
is truly enormous. I think it is of the order 2^(N^2).
> I am going to use "3clause" to mean "3CNF clause with three distinct terms".
>
> Let f(n) be the number of 2SAT instances for a 3CNF expression with m
> 3clauses. Suppose, in converting a 3SAT, you have processed m 3clauses,
> have f(m) 2SAT instances, and see another 3clause. It generates two
> alternative 2SAT clauses. For each of the f(m) existing instances, you
> need two new instances formed by appending each of the new clauses to
> it. Thus f(m+1) is 2*f(m). f(1) is 2 - a single 3clause results in two
> 2SAT instances. f(n) is 2^n.
You didn't take into account that there are only O(N^2) possible
2-clauses. This means the "new" clause from f(m) may have
already been chosen from a previous 3-clause.
Even so, the maximum number of 2SAT instances is exponential.
I want to know the minimum number of 2SAT instances required
such that every solution to a 2SAT instance in the set is also
a solution to the 3SAT instance and every solution to the 3SAT
instance is the solution of at least one of the 2SAT instances.
Obviously, I won't need more than 2^N 2SAT instances,
one for each satisfying assignment of the original 3SAT instance.
But, I may need far fewer because one 2SAT instance can
have an exponential number of solutions, all of which are
solutions to the original 3SAT instance.
If a 3SAT instance has exactly one satisfying assignment
I need no more than one 2SAT instance to emulate it.
I have already shown how i can emulate (a+b+c) using
the two 2SAT instance (a+b) and (a+c).
Actually, I think any 3SAT instance with only three variables
requires at most two 2SAT instances to emulate it.
Consider the 3SAT instance (a+b+c)(~a+~b+~c).
My set of two 2SAT instances:
1st instance: (a+b)(~a+~b)
2nd instance: (a+c)(~a+~c)
Every solution to either 2SAT instance is also a solution
to the 3SAT instance and any solution to the 3SAT
instance is a solution to at least one of the 2SAT
instances.
reas...@gmail.com
> On 16 Maj, 13:04, reaste...@gmail.com wrote:
> > I can "emulate" this 2+SAT expression
>
> > (a+~f)(b+~f)(~a+~b+f)
>
> > with two 2SAT instances:
>
> > 1st 2SAT: (a+~f)(b+~f)(~a+~b)
> > 2nd 2SAT: (a+~f)(b+~f)(~a+f)
>
> > Every satisfying assignment of any of these 2SAT instances
> > is also a solution for the 3SAT instance and any
> > satisfying assignment of the 3SAT instance
> > is also a solution of at least one of the 2SAT instances.
> > I only need the 2nd 2SAT expression to handle the
> > case where a,b, and f are all true.
> > (a+~f)(b+~f)(~a+~b) contains every solution to
> > (a+~f)(b+~f)(~a+~b+f) except when all variables are true.
>
> The "cut" is to use a single formula... besides that: a,b=true does't
> make 1st 2SAT true and there must be a typo in the 2nd 2SAT
> expression.
I am not claiming I can convert a 3SAT instance into a single
2SAT instance. I show how it is possible to create a set of
2SAT instances such that every satisfying assignment of
any 2SAT instance in the set is also a solution to the 3SAT
and every solution to the 3SAT instance is also a solution
of at least ONE of the 2SAT instances.
The 2nd 2SAT instance is false when a, b, and f are all false.
The original 3SAT instance is true when all variables are false.
The 1st 2SAT instance is true when all variables are false.
reas...@gmail.com
> I also found a new (to me) reduction.
> Is there a name for this reduction?
> (a+b+x)(a+b+y)(a+b+z)(~x+~y+~z) = (a+b)
I shouldn't post late at night.
The reduction rule is:
(a+b+x)(a+b+y)(a+b+z)(~x+~y+~z) = (a+b)(~x+~y+~z)
A variation on the rule:
(a+b+x)(a+b+y)(~x+~y+z)(~x+~y+~z) = (a+b)(~x+~y)
Has anyone seen this reduction rule or know what it is called?
reas...@gmail.com
> If a 3SAT instance has exactly one satisfying assignment
> I need no more than one 2SAT instance to emulate it.
If a 3SAT instance is unsatisfiable then my set is size 0.
If a 3SAT instance is unsatisfiable then every 2SAT
instance I can form must also be unsatisfiable.
I can form a 2SAT instance by choosing two literals
from every 3-clause.
Jan
I had a case of writing before reading syndrom - it can happen when I
read the words: "3SAT to 2SAT conversion", sorry.
My 3SAT formula is the function f := a ^ b, can you demonstrate the
reduction?
Regards, Jan
reas...@gmail.com
> My 3SAT formula is the function f := a ^ b, can you demonstrate the
> reduction?
The simplest is a single 2SAT instance: (a+b)(~a+b)(a+~b)
I need at least two 2SAT instances for the formula you
gave earlier:
(a+~f)(b+~f)(~a+~b+f)
cam be "emulated" with two 2SAT instances:
1st instance: (a+~f)(b+~f)(~a+~b)
2nd instance: (a+~f)(b+~f)(~a+f)
Any satisfying assignment of one of the 2SAT
instances is also a satisfying assignment of
the original 3SAT instance.
Any satisfying assignment of (a+~f)(b+~f)(~a+~b+f)
is also a satisfying assignment of either
(a+~f)(b+~f)(~a+~b) or (a+~f)(b+~f)(~a+f).