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
