26

There are several examples of problems where a parameterized algorithm performs well in practice. Let me mention two such problems. In the $k$-Path problem where we are looking for a simple path of length $k$. Alon, Yuster and Zwick [1] showed that this problem can be solved in $2^{O(k)}\cdot n$ time on $n$-vertex graphs. A weighted version of $k$-Path has ...


13

We can prove $\mathrm{NP\ne QP}$ unconditionally: $\mathrm{QP}$ is closed under quasipolynomial-time reductions, whereas $\mathrm{NP}$ is not (a simple padding argument shows that the closure of $\mathrm{NP}$ under quasipolynomial-time reductions includes all languages computable in nondeterministic quasipolynomial time, and this class strictly contains $\...


8

I think you're right about the first typo. I think the authors are actually fine on the other two questions. Imagine you've applied $f$ exactly $\log_2 m$ times and that $\varphi$ was unsatisfiable. At some first time $k<\log_2 m$, you know $\text{val}(f^{(k)}(\varphi))\leq 1-\epsilon_0$ because you double the gap while the value is at least $1-\epsilon_0$...


4

This is quite unlikely to hold, because $\mathrm{EXP_{poly}^{NEXP}}$ actually coincides with $\Theta^{\exp}_2$, the exponential analogue of the class $\Theta^P_2$, which is presumably a strict subclass of $\mathrm{EXP^{NP}}$ (which is the exponential analogue of $\Delta^P_2$). $\Theta^{\exp}_2$ can be variously defined as $$\Theta^{\exp}_2=\mathrm{EXP^{\|NP}=...


3

I stumbled upon this question now, many years later. In the interim the following paper has appeared: https://dl.acm.org/doi/10.1145/3278158 https://arxiv.org/abs/1704.08705 There the authors do precisely what Kaveh asks for in his question 2: they give a (uniform) TC0 algorithm for balancing, hence obtaining an alternative proof of the main result in Buss '...


1

As far as I have understood, you aim to develop a framework to capture the hardness of combinatorial problems in 3D. However, there are major problems in your question. Your first sentence lacks a couple of technical definitions: For a specific f(), I'm defining a term 'complexity', estimating how difficult is the given function to optimize. First, and the ...


Only top voted, non community-wiki answers of a minimum length are eligible