Convert 3-sat to n-sat with same variables on each clause

32 Views Asked by At

How to convert 3-sat with $n$ variables, where each clause is having only two operators: OR and NOT, and all the clauses connected with AND operator.

To n-sat where each clause has the same $n$ variables connected with OR and NOT operators, and all the clauses connected with AND operator.

The number of clauses is not important.

1

There are 1 best solutions below

0
On

Guess a solution $S$, if there is no negative $S$ then it must be a valid solution. Negative $S$ can be checked with a hashmap. Just keep guessing or start going over all the possible solutions until one is found.

This solves the problem in $O(N)$ where $N$ is the number of variables in all the clauses. It means that finding such a conversion is as easy as proving $P=NP$