0
$\begingroup$

I'm trying to understand how $3$-SAT problems are assigned complexity to try and get a better understanding of the P vs NP problem.

Would a polynomial-time solution to an increasing number of clauses but constant number of distinct literals resolve P vs NP?

Or, would an algorithm have to work in polynomial time in both the number of distinct literals and the number of clauses?

It seems like a 2-dimensional problem and I'm not sure in which 'direction' the P vs NP problem lies.

$\endgroup$

1 Answer 1

1
$\begingroup$

I assume you know about the problem SAT and that it is NP complete. This means that a polynomial algorithm for SAT would prove P=NP.

There is a way to reduce SAT to $3$-SAT. This means that any polynomial algorithm for $3$-SAT can be used to construct a polynomial algorithm for SAT. This means any polynomial algorithm for $3$-SAT would prove P=NP.

The input for $3$-SAT consists $n$ variables and $k$ clauses consisting of $3$ literals each. A literal is of the form $v$ or $\neg v$ for some variable $v$. A clause is of the form $a\lor b\lor c$ for some literals $a,b,c$. So the size of the input of a $3$-SAT instance is $n+3k$.

What we mean when we talk about a polynomial algorithm for $3$-SAT is an algorithm with running time $\mathcal{O}(p(n+3k))$ for some polynomial $p$. This means that the algorithm has to run in polynomial time in the number of variables, but also in the number of clauses and literals.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .