A Class of 3SAT Solvable in Polytime

From: Russell Easterly (logiclab_at_comcast.net)
Date: 03/16/05 

Date: Tue, 15 Mar 2005 20:38:18 -0800

A Class of 3SAT Solvable in Polytime

Let F() be a 3SAT instance.
If there is an assignment of variables
such that every clause in F() is
satisfied two or more times,
that assignment can be found
in polynomial time.

Proof:

Assume we have the 3-clause (A or B or C).
Consider the 2SAT instance:
(A or B) and (A or C) and (B or C).

This 2SAT instance is True if any two
variables in (A or B or C) are True.

Assume we transform every clause in F()
into the corresponding 2SAT clauses.
The resulting 2SAT instance will have
a satisfying assignment if and only if
F() has a satisfying assignment such
that every clause in F() is satisfied
at least twice.

Russell
- 2 many 2 count

Relevant Pages

  • Re: Optimizing Unit Clause Resolution
    ... A few unmatched literals is no big deal. ... I was looking for a way to optimize unit clause ... Satisfying a clause forces the assignment of three variables. ... At least two of these forced assignments will satisfy at least ...
    (comp.theory)
  • 3SAT - A Counting Solver 2
    ... U0,U1,U2 = clause variables ... we talk about the assignment ... represents a satisfying assignment to the ... Adding these new minterms: ...
    (comp.theory)
  • Re: Questions about Parity SAT
    ... Your "Parity SAT Positive" is an SAT ... instance where each literal exists only in its non-negated form in each ... What means that if each clause contains at least one ... Problem question is "Is there at least one assignment". ...
    (comp.theory)
  • A Class of 3SAT Solvable in Polytime
    ... If there is an assignment of variables ... in polynomial time. ... Assume we transform every clause in F ... Fhas a satisfying assignment such ...
    (sci.math)
  • A Class of 3SAT Solvable in Polytime
    ... If there is an assignment of variables ... in polynomial time. ... Assume we transform every clause in F ... Fhas a satisfying assignment such ...
    (comp.theory)