# Finding a Polynomial Time algorithm for the 3-SAT Problem

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?

• 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) May 6 at 16:27
• I am unsure of proving it formally and will try it out. At the moment, its just a theorization I have May 6 at 16:34
• 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?
– JimN
May 6 at 17:55
• 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 May 6 at 18:14
• As a rule of thumb, amateur mathematicians rarely break well established results.
– user16034
May 7 at 16:09