<p>In the definition on $KSUM$ problem we are given $n$ input integers and we have to decide if $K$ of them sum to $0$.</p>

<p>$KSUM$ is $FPT$ if there is a $O(f(K)poly(n))$ algorithm for it. However Downey and Fellows in their book give definition as</p>

<p><a href="https://i.sstatic.net/HfcZ6.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/HfcZ6.png" alt="enter image description here"></a></p>

<p>These two definitions do not seem to be entirely consistent.</p>

<p>We know $W[P]=FPT\implies W[1]=FPT$. </p>

<p>We also know this puts $KSUM$ is $FPT$.</p>

<p>Does it mean $KSUM$ is $FPT$ at a fixed $K$ and independent of length of integer inputs or can it also imply some asymptotic $FPT$ result where $K$ depends non-trivially on number of input integers and length of input integers?</p>

<ol>
<li><p>I looked for this information in Grohe's or Downey's book and I am unable to find this information and could someone weight in on this subtlety? That is we might have an algorithm for $KSUM$ that is $FPT$ if input integers have only $O(polylog(n))$ bits each. However if input bitlength is polynomial in $n$ or exponential in $K$ then the $FPT$ algorithm complexity might not be of shape $O(f(K)\cdot poly(n))$. This could still be $FPT$ under Downey's definition. Would such an algorithm still be considered $FPT$ for $KSUM$ as well? It should be but from the working definitions of $FPT$ for $KSUM$ in literature this is unclear.</p></li>
<li><p>Is it consistent $W[P]=FPT$ while $KSUM$ is not $FPT$ at bounded or fixed $K$?</p></li>
</ol>

CC BY-SA 4.0
2018-06-26T03:36:43.343Z
I'm not entirely sure if I understand.  Are you questioning whether it being in $FPT$ means that it's solvable in $f(k) \cdot n^c$ time vs $f(k) \cdot \vert x \vert ^c$ time where $n$ is the size of the set and $\vert x \vert$ is the total length of the input represented as a binary string?
Michael Wehar
CC BY-SA 4.0
2018-06-26T03:38:17.047Z
Anyway you look at it, the runtime has to depend on $\vert x \vert$ because you have to look at every bit of the input in order to determine if there exists a $k$-SUM.
Michael Wehar
CC BY-SA 4.0
2018-06-26T03:39:17.910Z
Or, are you asking how bounding the input integers affects the parameterized complexity of the $k$-SUM problem?
Michael Wehar
CC BY-SA 4.0
2018-06-26T06:01:27.160Z
@MichaelWehar I think '$FPT$ means that it's solvable in $f(k)\cdot n^c$ time vs $f(k)\cdot |x|^c$ time where $n$ is size of the set and $|x|$ is the total length of the input represented as a binary string' is the query 1. $f(k)\cdot |x|^c$ satisfies what Downey and Fellows have in their definition however when you say $KSUM$ is $FPT$ we usually think of $f(k)\cdot n^c$ (for example wiki says fastest $KSUM$ algorithm is in $n^O(K)$ time and it makes it look like $FPT$ in $KSUM$ case is $f(k)\cdot n^c$ definition which is not what Downey and Fellows have in definition.
Turbo
CC BY-SA 4.0
2018-06-26T06:06:42.847Z
@MichaelWehar Query 2. is about what exactly is the notion of $FPT$ in context of $KSUM$ mean with respect to parameter $K$ (will an algorithm that is $FPT$ in parameter $K$ that is asymptotic to size of the set $n$ (not input length $|x|$) provide $KSUM$ in $FPT$)?
Turbo
CC BY-SA 4.0
2018-06-26T07:27:03.987Z
What does this have to do with the communication complexity polynomial hierarchy? Please, do not change questions into unrelated completely different questions. Ask a new question instead.
Emil Jeřábek
CC BY-SA 4.0
2018-06-26T08:26:49.957Z
@EmilJeřábek I could not ask any new questions or else I would have. The system blocked me and this is the best I could do and I already raised a flag with moderators few days back and nothing happened.
Turbo
CC BY-SA 4.0
2018-06-26T08:40:48.350Z
Is that so? The system blocks you for a reason. Trying to circumvent it like this is cheating.
Emil Jeřábek
CC BY-SA 4.0
2018-06-26T08:41:41.600Z
@EmilJeřábek It blocked me because I was getting downvotes without improvement comments (like you are doing right now) and I just changed bad questions. What is wrong with it?
Turbo
CC BY-SA 4.0
2018-06-26T10:48:33.157Z
What do you mean by “like you are doing right now”? I *am* commenting right now. Anyway, stop blaming others for your shortcomings. The system is designed to block users that post poor questions, and that’s exactly what you do. You posted a large number of poorly written questions that show lack of research effort (both in terms of literature search and it terms of independent thinking), lack of understanding of elementary basics (that would be better served at cs.stackexchange.com), and that are often mathematically incoherent and formulated in an incomprehensible way. People, ...
Emil Jeřábek
CC BY-SA 4.0
2018-06-26T10:51:04.767Z
Ok I will remove my post.
Turbo
<cc.complexity-theory><big-picture><polynomial-time><fixed-parameter-tractable><subset-sum>
What definition for $FPT$ algorithm for $KSUM$ gives $W[P]=FPT\implies KSUM$ is $FPT$?
Turbo
# What definition for $FPT$ algorithm for $KSUM$ gives $W[P]=FPT\implies KSUM$ is $FPT$?

(Asked by: username_0 on 2018-06-15)

In the definition on $KSUM$ problem we are given $n$ input integers and we have to decide if $K$ of them sum to $0$.

$KSUM$ is $FPT$ if there is a $O(f(K)poly(n))$ algorithm for it. However Downey and Fellows in their book give definition as

[![enter image description here](https://i.sstatic.net/HfcZ6.png)](https://i.sstatic.net/HfcZ6.png)

These two definitions do not seem to be entirely consistent.

We know $W[P]=FPT\implies W[1]=FPT$.

We also know this puts $KSUM$ is $FPT$.

Does it mean $KSUM$ is $FPT$ at a fixed $K$ and independent of length of integer inputs or can it also imply some asymptotic $FPT$ result where $K$ depends non-trivially on number of input integers and length of input integers?

1. I looked for this information in Grohe's or Downey's book and I am unable to find this information and could someone weight in on this subtlety? That is we might have an algorithm for $KSUM$ that is $FPT$ if input integers have only $O(polylog(n))$ bits each. However if input bitlength is polynomial in $n$ or exponential in $K$ then the $FPT$ algorithm complexity might not be of shape $O(f(K)\cdot poly(n))$. This could still be $FPT$ under Downey's definition. Would such an algorithm still be considered $FPT$ for $KSUM$ as well? It should be but from the working definitions of $FPT$ for $KSUM$ in literature this is unclear.
2. Is it consistent $W[P]=FPT$ while $KSUM$ is not $FPT$ at bounded or fixed $K$?

**Tags:** cc.complexity-theory, big-picture, polynomial-time, fixed-parameter-tractable, subset-sum
> **Comments:**
> **username_1**: I'm not entirely sure if I understand.  Are you questioning whether it being in $FPT$ means that it's solvable in $f(k) \cdot n^c$ time vs $f(k) \cdot \vert x \vert ^c$ time where $n$ is the size of the set and $\vert x \vert$ is the total length of the input represented as a binary string?  
> **username_1**: Anyway you look at it, the runtime has to depend on $\vert x \vert$ because you have to look at every bit of the input in order to determine if there exists a $k$-SUM.  
> **username_1**: Or, are you asking how bounding the input integers affects the parameterized complexity of the $k$-SUM problem?  
> **username_0**: @MichaelWehar I think '$FPT$ means that it's solvable in $f(k)\cdot n^c$ time vs $f(k)\cdot |x|^c$ time where $n$ is size of the set and $|x|$ is the total length of the input represented as a binary string' is the query 1. $f(k)\cdot |x|^c$ satisfies what Downey and Fellows have in their definition however when you say $KSUM$ is $FPT$ we usually think of $f(k)\cdot n^c$ (for example wiki says fastest $KSUM$ algorithm is in $n^O(K)$ time and it makes it look like $FPT$ in $KSUM$ case is $f(k)\cdot n^c$ definition which is not what Downey and Fellows have in definition.  
> **username_0**: @MichaelWehar Query 2. is about what exactly is the notion of $FPT$ in context of $KSUM$ mean with respect to parameter $K$ (will an algorithm that is $FPT$ in parameter $K$ that is asymptotic to size of the set $n$ (not input length $|x|$) provide $KSUM$ in $FPT$)?  
> **username_2**: What does this have to do with the communication complexity polynomial hierarchy? Please, do not change questions into unrelated completely different questions. Ask a new question instead.  
> **username_0**: @EmilJeřábek I could not ask any new questions or else I would have. The system blocked me and this is the best I could do and I already raised a flag with moderators few days back and nothing happened.  
> **username_2**: Is that so? The system blocks you for a reason. Trying to circumvent it like this is cheating.  
> **username_0**: @EmilJeřábek It blocked me because I was getting downvotes without improvement comments (like you are doing right now) and I just changed bad questions. What is wrong with it?  
> **username_2**: What do you mean by “like you are doing right now”? I *am* commenting right now. Anyway, stop blaming others for your shortcomings. The system is designed to block users that post poor questions, and that’s exactly what you do. You posted a large number of poorly written questions that show lack of research effort (both in terms of literature search and it terms of independent thinking), lack of understanding of elementary basics (that would be better served at cs.stackexchange.com), and that are often mathematically incoherent and formulated in an incomprehensible way. People, ...  
> **username_0**: Ok I will remove my post.  

---

## 0 answers

