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
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.