# Tag Info

### Do any quantum algorithms improve on classical SAT?

Indeed, as wwjohnsmith1 said, you can get a square root speed-up over Schöning's algorithm for 3-SAT, but also more generally for Schöning's algorithm for k-SAT. In fact, many randomized algorithms ...
• 13.3k
Accepted

### Do any quantum algorithms improve on classical SAT?

I think one can obtain a non-trivial upper bound from quantum computing by speeding up the randomized algorithms of Schöning for 3-SAT. The algorithm of Schöning runs in time $(4/3)^n$ and ...
• 316

### Problems that started out with hopelessly intractable algorithms that have since been made extremely efficient

Computing a generating set of invariants (sometimes called the computational problem of "Noether's Normalization Lemma") for the action of $SL_3$ on an $n$-dimensional vector space $V$. (You ...
• 35.7k

### Problems that started out with hopelessly intractable algorithms that have since been made extremely efficient

The task of unification went from an exponential solution to linear time in the timespan of about a decade. The original exponential algorithm was a corner-stone for symbolic AI approaches and enabled ...
• 271
Accepted

### NP-hard problems with very fast exponential-time algorithms

The desired property holds for Independent Set (and probably other problems) in graphs of suitably bounded tree width. Fix any constant $\epsilon>0$ and consider the Independent Set problem ...
• 8,223

### Questions regarding SETH

The subtlety comes in where we introduce the notion of "harder". The reduction showing that SAT can be reduced to Hamiltonian Cycle shows that the latter is "harder" up to polynomial factors. In doing ...
• 1,624

• 14.8k

Accepted

### Reference request: complexity of $k$-partite $k$-SAT

Claim: If there exists an $\epsilon > 0$ such that for every $k'$, $k'$-partite $k'$-SAT can be solved in $2^{n(1-\epsilon)}$ time, then SETH fails. Proof: Suppose such an algorithm exists. We ...
• 3,236
Accepted

### What is the worst-case runtime complexity to transform a NFA to DFA via Rabin-Scott's power set construction?

At first glance this looks like a mistake in Wikipedia (it wouldn't be the first one), but I think the time bound there is actually correct, with two assumptions and one small idea. The assumption is:...
• 50.2k

### How many distinct colors are needed to lower-bound the choosability of a graph?

As a bit of unashamed self-promotion, Marthe Bonamy and I found more negative answers. In particular, Theorem 4 of http://arxiv.org/abs/1507.03495 improves upon the aforementioned result of Král' and ...
• 1,952
Accepted

### What is the fastest known algorithm for computing a 1.99-approximation of Vertex Cover?

I think for getting 1.99-approximation algorithm this paper by Manurangsi and Trevisan, has the current fastest algorithm.
• 387
Accepted

• 14.8k
Accepted

### Oracle comparing $EXP$ with $UP$

$\mathsf{UP} \neq \mathsf{EXP}$ is open. A UP-generic oracle* should make $\mathsf{P} \neq \mathsf{UP} = \mathsf{EXP}$, and since $\mathsf{UP} \subseteq \mathsf{\oplus P} \subseteq \mathsf{EXP}$ ...
• 35.7k
Accepted

### Consequences of faster parameterized integer programming

An instance of CNF-SAT with $k$ variables can easily be written as a 0/1 integer linear program over the same variable set, since a clause such as $x_1 \vee x_3 \vee \neg x_4 \vee \neg x_6$ naturally ...
• 5,225
Accepted

### Is there a W[1]-hard problem that can be solved in $2^{o(n)}$ time?

How about Planar Capacitated Dominating Set? It is W[1]-hard (see the paper by Bodlaender, Lokshtanov, Penninkx in IWPEC 2009), but should be solvable in $2^{O(\sqrt{n}\log n)}$ by using the fact that ...
• 3,094

### Questions regarding SETH

Cygan, Kratsch and Nederlof give a $(2+\sqrt{2})^{\texttt{pw}} n^{O(1)}$ algorithm for hamiltonicity on graphs with $n$ vertices and pathwidth $\texttt{pw}$ (assuming you are given the pathwidth ...
• 14.1k

### Most general setting for fine-grained exponential-time complexity classes?

(Just now noticed this question.) There are a lot of questions in the above question. I will try to just address the last few. Might it be the case that a RAM program can solve general CNF-SAT in ...
• 26.4k
Assuming SETH, the problem is not solvable in time $O\bigl(2^{(1-\epsilon)n}\mathrm{poly}(l)\bigr)$ for any $\epsilon>0$. First, let me show that this is true for the more general problem where \$\...