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?

  • 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$
    – user555045
    Commented May 6, 2023 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$ Commented May 6, 2023 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
    Commented May 6, 2023 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$ Commented May 6, 2023 at 18:14
  • 2
    $\begingroup$ As a rule of thumb, amateur mathematicians rarely break well established results. $\endgroup$
    – user16034
    Commented May 7, 2023 at 16:09


Your Answer

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