# Relation between $k$-sum failure and $P=NP$

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

• 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). Mar 28 at 16:37
• @Tassle yes correct I am asking for possible effective converse with a bound on $k$ given speed limits on $SAT$. Mar 28 at 17:14
• 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$. Mar 29 at 14:06
• @Tassle So you are saying if $\alpha=1+\epsilon$, then $3$-SUM conjecture fails? Can you elaborate your comment for a full answer? Mar 29 at 14:27
• 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. Mar 30 at 10:40