<p>Complexity zoo in <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:E#eptas" rel="nofollow noreferrer">https://complexityzoo.uwaterloo.ca/Complexity_Zoo:E#eptas</a> has the following:</p>

<p><span class="math-container">$FPT = XPuniform\implies EPTAS = PTAS$</span>.</p>

<p><a href="https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.456.2729&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">Fundamentals of Parametrized complexity</a> on page <span class="math-container">$534$</span> has</p>

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

<p>which from "we will only look at XP and
remark that all the results hold with no change for uniform XP as well. By
standard diagonalization, we have the following basic result:</p>

<p>Proposition <span class="math-container">$27.3.1$</span>. FPT is a proper subset of XP."</p>

<p>means <span class="math-container">$FPT$</span> is a proper subset of <span class="math-container">$XP_{uniform}$</span> as well.</p>

<ol>
<li><p>Is this correct information? If so this result has been known for a long time. So is there any updates that need to be made to complexity zoo section <a href="https://complexityzoo.uwaterloo.ca/Complexity_Zoo:E#eptas" rel="nofollow noreferrer">https://complexityzoo.uwaterloo.ca/Complexity_Zoo:E#eptas</a> and is there any consequences to approximation algorithms because of this?</p></li>
<li><p>Does <span class="math-container">$FPT=W[P]$</span> have any consequences to approximation algorithms? I see only reverse consequences in complexity zoo:</p></li>
</ol>

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

CC BY-SA 4.0
2020-02-12T05:43:00.970Z
We should have $FPT \neq XP_{uniform}$.  Suppose for sake of contradiction that they were equal.  Then, it would follow that there exists $c$ such that $PTIME = DTIME(n^c)$.  This cannot be true by the time hierarchy theorem so we get a contradiction.
Michael Wehar
CC BY-SA 4.0
2020-02-12T05:58:34.303Z
I believe that if $FPT = W[P]$, then we would get faster algorithms for circuit SAT.  This is mentioned on the Wikipedia page: https://en.wikipedia.org/wiki/Parameterized_complexity .  If $FPT = W[P]$ were true, then we might also obtain new circuit lower bounds.
Michael Wehar
CC BY-SA 4.0
2020-02-13T05:21:47.100Z
@MichaelWehar Yes $FPT=W[P]$ is stronger than non-$ETH$.
Turbo
<cc.complexity-theory><reference-request><complexity-classes><approximation-algorithms><parameterized-complexity>
$XP_{\text{uniform}}=FPT$ and update to $EPTAS$ section in complexity zoo?
Turbo
# $XP_{\text{uniform}}=FPT$ and update to $EPTAS$ section in complexity zoo?

(Asked by: username_0 on 2019-05-22)

Complexity zoo in <https://complexityzoo.uwaterloo.ca/Complexity_Zoo:E#eptas> has the following:

$FPT = XPuniform\implies EPTAS = PTAS$.

[Fundamentals of Parametrized complexity](https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.456.2729&rep=rep1&type=pdf) on page $534$ has

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

which from "we will only look at XP and
remark that all the results hold with no change for uniform XP as well. By
standard diagonalization, we have the following basic result:

Proposition $27.3.1$. FPT is a proper subset of XP."

means $FPT$ is a proper subset of $XP\_{uniform}$ as well.

1. Is this correct information? If so this result has been known for a long time. So is there any updates that need to be made to complexity zoo section <https://complexityzoo.uwaterloo.ca/Complexity_Zoo:E#eptas> and is there any consequences to approximation algorithms because of this?
2. Does $FPT=W[P]$ have any consequences to approximation algorithms? I see only reverse consequences in complexity zoo:

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

**Tags:** cc.complexity-theory, reference-request, complexity-classes, approximation-algorithms, parameterized-complexity

> **Comments:**
> **username_1**: We should have $FPT \neq XP_{uniform}$.  Suppose for sake of contradiction that they were equal.  Then, it would follow that there exists $c$ such that $PTIME = DTIME(n^c)$.  This cannot be true by the time hierarchy theorem so we get a contradiction.  
> **username_1**: I believe that if $FPT = W[P]$, then we would get faster algorithms for circuit SAT.  This is mentioned on the Wikipedia page: https://en.wikipedia.org/wiki/Parameterized_complexity .  If $FPT = W[P]$ were true, then we might also obtain new circuit lower bounds.  
> **username_0**: @MichaelWehar Yes $FPT=W[P]$ is stronger than non-$ETH$.  

---

## 0 answers

