<p>If <span class="math-container">$P=NP$</span> then <span class="math-container">$W[1]=FPT$</span> holds. Hence <span class="math-container">$k$</span>-sum conjecture fails at a finite <span class="math-container">$k$</span>. What can we say about the time complexity of <span class="math-container">$SAT$</span> and the lowest <span class="math-container">$k$</span> at which <span class="math-container">$k$</span>-sum conjecture fails?</p>
<p>In particular, do <span class="math-container">$3$</span>-sum and <span class="math-container">$4$</span>-sum conjectures fail if <span class="math-container">$P=NP$</span> and <span class="math-container">$3SAT$</span> is in <span class="math-container">$O(n^a)$</span> time for some upper bound <span class="math-container">$a\geq1$</span>?</p>

CC BY-SA 4.0
2024-03-28T16:37:50.523Z
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).
Tassle
CC BY-SA 4.0
2024-03-28T17:14:09.213Z
@Tassle yes correct I am asking for possible *effective* converse with a bound on $k$ given speed limits on $SAT$.
Turbo
CC BY-SA 4.0
2024-03-29T14:06:04.590Z
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$.
Tassle
CC BY-SA 4.0
2024-03-29T14:27:14.490Z
@Tassle So you are saying if $\alpha=1+\epsilon$, then $3$-SUM conjecture fails? Can you elaborate your comment for a full answer?
Turbo
CC BY-SA 4.0
2024-03-29T18:49:39.083Z
$\epsilon\in[0,1)$
Turbo
CC BY-SA 4.0
2024-03-30T10:40:17.890Z
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.
Tassle
CC BY-SA 4.0
2024-03-30T19:37:05.313Z
Could you please recall the formulation of the $k$-sum conjecture? This would make the question a but more self-contained.
Christian Komusiewicz
<cc.complexity-theory><sat><big-picture><parameterized-complexity><fixed-parameter-tractable>
Relation between $k$-sum failure and $P=NP$
Turbo
# Relation between $k$-sum failure and $P=NP$

(Asked by: username_0 on 2024-03-27)

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

**Tags:** cc.complexity-theory, sat, big-picture, parameterized-complexity, fixed-parameter-tractable

> **Comments:**
> **username_1**: 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).  
> **username_0**: @username_1 yes correct I am asking for possible *effective* converse with a bound on $k$ given speed limits on $SAT$.  
> **username_1**: 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$.  
> **username_0**: @username_1 So you are saying if $\alpha=1+\epsilon$, then $3$-SUM conjecture fails? Can you elaborate your comment for a full answer?  
> **username_0**: $\epsilon\in[0,1)$  
> **username_1**: 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.  
> **username_2**: Could you please recall the formulation of the $k$-sum conjecture? This would make the question a but more self-contained.  

---

## 0 answers

