# Tag Info

## Hot answers tagged cc.complexity-theory

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