A Class of 3SAT Solvable in Polytime

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

  • Next message: Jackson Pearcy: "Re: What are numbers?" 
    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

  • Next message: Jackson Pearcy: "Re: What are numbers?"

    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.logic)
    • 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)