38
votes
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
30
votes
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
22
votes
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
17
votes
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
16
votes
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
14
votes
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
13
votes
Problems with Unknown Single Exponential Time Agorithms
In the Graph Homomorphism problem, the input is two graphs $G$ and $H$ and the question is whether there is a mapping $h$ from the vertices of $G$ to the vertices of $H$ such that for every edge $uv\...
- 4,986
13
votes
Accepted
Examples of problems where exponential algorithms run faster than polynomial algorithms for practical sizes?
How bout the simplex algorithm for linear programming?
In many occasions it is used in practice.
Edited to add:
I think it's more of a "worse-case exponential algorithm" which runs ...
- 9,378
12
votes
Accepted
EXP-Complete Problems vs Subexponential Algorithms
Due to popular demand, I’m converting my comment to an answer.
A simple padding argument shows that for every constant $\epsilon>0$, there exist EXP-complete problems in $\mathrm{DTIME}(2^{n^\...
- 14.8k
12
votes
Examples of problems where exponential algorithms run faster than polynomial algorithms for practical sizes?
The fastest algorithm known for the problem of identifying whether a graph has a knotless embedding is due to Miller and Naimi, and is exponential-time. Robertson-Seymour theory says that there is an $...
- 23.5k
12
votes
Problems that started out with hopelessly intractable algorithms that have since been made extremely efficient
I can think of two additional examples to the ones mentioned above, although I'm not sure that they were ever considered intractable.
Lovász Local Lemma - The Lovász local lemma (LLL) is a powerful ...
11
votes
Problems with Unknown Single Exponential Time Agorithms
Update 28 Sep 2020: This has been resolved by Wiebking in SODA '20, where he gave a $2^{O(n)}$-time algorithm, with no remaining dependence on $|G|$. (I'll leave up the rest of the answer for ...
- 35.7k
10
votes
Problems with Unknown Single Exponential Time Agorithms
Computing the crossing number of a graph. Existing exact algorithms involve formulating it as an integer linear program with a number of variables cubic in the number of edges [Chimani et al, ESA 2008]...
- 50.2k
10
votes
$\overline{SAT} \in NTIME(subexp)$?
A new preprint by Carmosino et al. introduces the Nondeterministic Strong Exponential Time Hypothesis (NSETH) which makes the conjecture that there are no $\text{NTIME}[2^{(1-\varepsilon) n}]$ ...
- 4,493
10
votes
Problems that started out with hopelessly intractable algorithms that have since been made extremely efficient
Interior point algorithms for LP. Although they came after Ellipsoid they are a different class of provably polynomial-time algorithms. And despite initial skepticism about their ability to outperform ...
- 6,649
10
votes
Problems that started out with hopelessly intractable algorithms that have since been made extremely efficient
Until Francis's QR algorithm was discovered, computing the eigenvalues was often done by first computing the characteristic polynomial, which was often an expensive and inaccurate endeavor, as has ...
- 101
9
votes
Accepted
Does two-sided error have more capability than one-sided error?
This isn't my area, so many apologies if I say something incorrect:
1) "What evidence do we have that $\mathsf{BPP}\subseteq \mathsf{REXP}$?"
Isn't this unconditionally true? It should follow from $\...
- 740
8
votes
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
8
votes
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
8
votes
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
8
votes
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
7
votes
Accepted
Example of context-free grammar that triggers exponential behaviour without memoization in RD parsers
Here is a grammar that should meet your specification, though it
generates the very simple language $a^+(b+c)$. (A simpler grammar has been added below)
$S \rightarrow ab \mid aBb \mid ac \mid aCc$
$...
- 1,502
7
votes
Accepted
Two DFA intersection emptiness connections to SETH & L vs P
The "inverse" is almost the same as
SAT is solvable in $O(2^{(1-\epsilon)n})$ time implies the intersection problem is solvable in
$O(n^{2-\epsilon})$ time.
To show this, it seems that you would ...
- 4,900
7
votes
Oracle comparing $EXP$ with $UP$
The quoted Beigel, Buhrman, and Fortnow paper gives a solution to 2 in Theorem 1.8: there is an oracle relative to which $\mathrm{P=Mod_3P}$ (which implies $\mathrm{P=UP}$), and $\mathrm{\oplus P=NP=...
- 14.8k
7
votes
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
7
votes
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
6
votes
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
6
votes
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
6
votes
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
6
votes
Accepted
The problem of deciding whether a monotone CNF implies a monotone DNF
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 $\...
- 14.8k
Only top scored, non community-wiki answers of a minimum length are eligible