If $P=NP$ then $W[1]=FPT$ holds. Hence $k$-sum conjecture fails at a finite $k$. What can we say about the time complexity of $SAT$ and the lowest $k$ at which $k$-sum conjecture fails?

In particular, do $3$-sum and $4$-sum conjectures fail if $P=NP$ and $3SAT$ is in $O(n^a)$ time for some upper bound $a\geq1$?

  • 1
    $\begingroup$ This is the other direction than what you are asking, but if you can solve $k$-sum in $n^{o(k)}$ time, then the Exponential Time Hypothesis (ETH) is false (see Patrascu and Williams, On the possibility of faster SAT algorithms). $\endgroup$
    – Tassle
    Mar 28 at 16:37
  • $\begingroup$ @Tassle yes correct I am asking for possible effective converse with a bound on $k$ given speed limits on $SAT$. $\endgroup$
    – Turbo
    Mar 28 at 17:14
  • $\begingroup$ If I recall correctly, you can assume without loss of generality that the integers in your $k$-sum instance are in the range $-n^k$ to $n^k$ via hashing tricks. From there it is not too hard to encode such an instance of $k$-sum into a $3$-SAT instance with $O(kn\log n)$ clauses (using adder circuits and the like). This would imply that the $k$-sum conjecture fails whenever $\lceil k/2 \rceil > \alpha$. $\endgroup$
    – Tassle
    Mar 29 at 14:06
  • $\begingroup$ @Tassle So you are saying if $\alpha=1+\epsilon$, then $3$-SUM conjecture fails? Can you elaborate your comment for a full answer? $\endgroup$
    – Turbo
    Mar 29 at 14:27
  • 1
    $\begingroup$ If I didn't make any mistakes, then yes. I'll try to post an answer in a week or so if no one else has by then. $\endgroup$
    – Tassle
    Mar 30 at 10:40


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.