Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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.
