Skip to main content
41 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 ...
Robin Kothari's user avatar
31 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 ...
wwjohnsmith1's user avatar
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 ...
Joshua Grochow's user avatar
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 ...
liori's user avatar
  • 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 ...
Neal Young's user avatar
  • 10.8k
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 ...
Yonatan N's user avatar
  • 1,642
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^\...
Emil Jeřábek's user avatar
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 ...
user3209423940248's user avatar
12 votes
Accepted

What are some examples of decidable Natural Problems outside of EEXP?

Let me give a few examples in the form of decision procedures for natural first-order theories. By a result of Berman [1], Presburger arithmetic $\mathrm{Th}(\mathbb N,+)$ (or $\mathrm{Th}(\mathbb Z,+,...
Emil Jeřábek's user avatar
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 ...
Chandra Chekuri's user avatar
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 ...
Joe Boy's user avatar
  • 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 $\...
Jason Gaitonde's user avatar
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.
A.2's user avatar
  • 397
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 ...
daniello's user avatar
  • 3,266
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=...
Emil Jeřábek's user avatar
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}$ ...
Joshua Grochow's user avatar
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 ...
Bart Jansen's user avatar
  • 5,275
6 votes
Accepted

Correctness of AKS algorithm for shortest vector problem

What you seem to be missing is that $\tau$ is not applied to all "green" vectors. Instead, think of every point $x_i$ as having a coin attached to it. Before you use $x_i$ in the algorithm, you toss ...
Sasho Nikolov's user avatar
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 $\...
Emil Jeřábek's user avatar
6 votes

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

I wanted to say Linear Programming, but although theoretical algorithm that are as fast as matrix multiplication have now been found, in practice people are still mostly using the exponential Simplex ...
Thomas Ahle's user avatar
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 ...
Michael Lampis's user avatar
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 ...
Ryan Williams's user avatar
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 ...
Yuval Filmus's user avatar
  • 14.5k
6 votes

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

Algorithms that computed the position of planets when they thought the earth was the center of the universe versus when they realized the sun was the center of the solar system. :-) While that's not ...
Neil Robertson's user avatar
6 votes
Accepted

Best known algorithm for NEXP-complete problem

For every $\epsilon>0$, there exists an NEXP-complete language $L_\epsilon$ in $\mathrm{NTIME}(2^{n^\epsilon})$, and therefore in $\mathrm{DTIME}(2^{2^{n^\epsilon}})$, which is below $2^{o(2^n)}$. ...
Emil Jeřábek's user avatar
5 votes

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

Perhaps a good example is Graph Isomorphism testing, also discussed here: Fastest known deterministic algorithm for the undirected Graph Isomorphism problem and here: https://people.cs.uchicago.edu/~...
Avi Tal's user avatar
  • 1,606
5 votes

What are some examples of decidable Natural Problems outside of EEXP?

The Petri nets/Vector Addition Systems reachability problem is not primitive recursive; more precisely, it is complete for the class $\mathcal F_\omega$ of the fast-growing hierarchy (essentially the ...
Emil Jeřábek's user avatar
4 votes

Problems with Unknown Single Exponential Time Agorithms

The problem of testing whether a given integer linear program $L$ with $n$ variables has a feasible solution can be solved using $n^{2.5n+o(n)}\cdot |L|$ arithmetic operations. It is a major open ...
Christian Komusiewicz's user avatar
4 votes

Problems with Unknown Single Exponential Time Agorithms

Tensor Isomorphism. The best-known algorithm for 3-Tensor Isomorphism over $\mathbb{F}_q$ takes time $q^{\Theta(n^2)}$, and over $\mathbb{R}$ or $\mathbb{C}$ takes times $2^{\Theta(n^2)}$. (The same ...
Joshua Grochow's user avatar
4 votes

On $\text{ETH}$ with $m$ as parameter: consequences of algorithm running in time $2^{\delta m}$ where $\delta \to 0$ as $k \to \infty$

This is an answer to the updated question (the original question seems harder). Let $\mu'_k$ be the smallest constant such that $k$-SAT that has clauses of length exactly $k$ and no trivial clauses ...
Laakeri's user avatar
  • 1,786

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