0
$\begingroup$

Let us consider m clauses containing 3 variables each i.e. A1,A2,A3...Am . Let the total literals in consideration be n. Then each clause :

Ai = (xr $\lor$ xs $\lor$ xt)

where 1 $\le$ r,s,t $\le$n and each literal can take a boolean value or its negation. Our expression $\phi$ which we need to satisfy hence looks as follows :

$\phi$ = (A1 $\land$ A2 $\land$ A3 $\land$ .... Am)

We now define an array B where each index stores sets of n tuples which are defined later. We now begin with the procedure. Assign all the boolean literals x1, x2, x3 .... xn as true and evaluate $\phi$.

  1. If $\phi$ is true, we are done. Else initialize i=1 and set B[1]={(-1,-1,.....-1)} such that B[1] is a set of a n-tuple.
  2. Evaluate Ai by trying all 8 combinations of assignments for the 3 literals. One of these assignments will make Ai false. Consider Ai = (xr $\lor$ xs $\lor$ xt) . Set the r,s and t the element in the tuple at B[i] as 0 or 1 as per the assignment that makes the clause false. If i is equal to 1, go to step 2.
  3. Perform a merge operation between B[i-1] and B[i]. For each element in B[i-1], compare it with the only element in B[i] at coordinates where neither elements contain -1. For example if we have to merge the tuples (0,0,-1,0) and (-1,0,0,1), we ignore coordinates 1 and 3. We compare the remaining coordinates i.e. 2 and 4. If among the remaining coordinates, they ONLY differ at 1 position, then $\phi$ is unsatisfiable. Else if for all elements in B[i-1], we find no such condition with the element in B[i], we add all elements from B[i-1] to B[i] .
  4. Increment i by 1, If i=m i.e. we have evaluated all clauses, goto Step 5. Else Go back to step 2.
  5. $\phi$ is satisfiable (exit)

I am an undergraduate student and I was trying to see why the 3-SAT problem was NP-hard. Is this a valid way to evaluate if $\phi$ is satisfiable or not in polynomial time? Or have I gone wrong somewhere?

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ I can believe that this detects some unsatisfiable formulas, but can you give an argument why this is a complete procedure? (ie definitely detects satisfiability) $\endgroup$
    – harold
    May 6 at 16:27
  • $\begingroup$ I am unsure of proving it formally and will try it out. At the moment, its just a theorization I have $\endgroup$
    – Pathlessbark8
    May 6 at 16:34
  • $\begingroup$ does B[m] begin with one n-tuple (-1,...-1) ? And every iteration it can have up to 8 more assignments (n-tuples) added to it? And the algorithm ends if the size of B[m] = $2^n$? Is this correct? $\endgroup$
    – JimN
    May 6 at 17:55
  • $\begingroup$ B[i] begins with one n-tuple . For 3 literals in each clause, there will exist only one assignment which doesn't satisfy it. So we add only one of the assignments after checking all 8. The algorithm ends if i is equal to m or if the condition in bold holds true $\endgroup$
    – Pathlessbark8
    May 6 at 18:14
  • 2
    $\begingroup$ As a rule of thumb, amateur mathematicians rarely break well established results. $\endgroup$
    – user16034
    May 7 at 16:09

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.