34
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 for k-SAT can be implemented quadratically faster on a quantum computer.
The reason for this general phenomenon is the following. Many randomized algorithms for ...
24
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 using standard amplitude amplification techniques one can obtain a quantum algorithm that runs in time $(2/\sqrt{3})^n=1.15^n$ which is significantly faster than ...
18
SETH says that for all $\delta < 1$ there is a $k$ such that $k$-SAT requires $2^{\delta n}$ time to be solved in the worst-case. The computational model is generally taken to be the random-access machine or pointer machine model, which allows for $O(\log N)$ time access to a storage of $N$ items, and is generally assumed to also be probabilistic with ...
17
It is possible ;-)
It would give new circuit lower bounds. Since you are making a pretty strong assumption this could follow from the seminal work by Impagliazzo, Kabanets, and Wigderson, I haven't checked.
If you use Williams' approach, tightened here, you get a lower bound of $n^{1+\Omega(1)}$ for a function on $n$ bits in the class E$^{NP}$. (For this ...
16
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 restricted to graphs of tree width at most $n \log_2(1+\epsilon) = \Theta(\epsilon n)$, where $n$ is the number of vertices. Call this problem $\Pi_\epsilon$.
Lemma ...
14
If $m$ is superlinear, such an algorithm would disprove the Strong Exponential Time Hypothesis, since formulas in conjunctive normal form are a special case of 0-1 programming and the Sparsification Lemma allows us to reduce $k$-SAT to CNF-SAT on linearly many clauses.
However, there is an algorithm due to Impagliazzo, Paturi, and myself that can solve such ...
13
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 the reduction, we may very well increase the variable $n$ in question substantially (by some polynomial). And the canonical reductions do blow it up quite ...
13
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 efficiently on practical instances/distributions rather than runs faster on practical sized adversarial instances.
12
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 $O(n^3)$ algorithm for this problem; however, to write it down we would need to know the list of forbidden minors for knotless embeddings. However, even if we ...
12
An optimal solution lies on some face. So, we can go through all the faces of the cube, and find all stationary points on each of the faces.
Here is a more concrete procedure. A face of the cube can be characterized by two disjoint index sets $I_0$ and $I_1$. For $i \in I_0$, we fix $x_i = 0$, and for $i \in I_1$ we fix $x_i = 1$. Let $\tilde{x}$ ...
12
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^\epsilon})$. Indeed, fix an arbitrary EXP-complete problem $L$, and assume that it is computable in time $2^{n^c}$. Let $d>c/\epsilon$, and consider the problem
$$...
11
The case of $m = c \log n$ is in $n^{O(c)}$ time as noted by Yuval, but also note for $k = O(1)$ you can solve the problem in $O(n^k \cdot m)$ time (polynomial time) by exhaustive search. Assuming the Strong Exponential Time Hypothesis (that CNF-SAT on formulas with $N$ variables and $O(N)$ clauses requires at least $2^{N-o(N)}$ time), these two time bounds ...
11
When $m = O(\log n)$, you can use dynamic programming to find the optimum in polynomial time. The table contains Boolean-valued cells $T_{\ell,X}$ for each $\ell \in \{0,\ldots,k\}$ and $X \subseteq \mathcal{U}$, indicating whether there are $\ell$ sets which cover the elements in $X$.
When $m = O(\sqrt{n})$, say $m \leq C\sqrt{n}$, the problem remains NP-...
10
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}]$ algorithms for DNF-TAUT. NSETH is of course an even stronger assumption than "NETH" which you ask about, and still appears to be consistent with everything we know so ...
9
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 $\mathsf{BPP}\subseteq \mathsf{EXP}$, and in fact by Sipser-Gács-Lautemann $\mathsf{BPP}\subseteq \Sigma^p_2\cap \Pi_2^p$.
2) "What consequences does $\mathsf{...
8
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: the alphabet size is constant, so you can ignore the $b$ factor in the runtime and output size. The second assumption is: you can represent the output DFA as ...
8
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\in E(G)$ we have that $h(u) h(v)\in E(H)$.
The problem can be solved in time $O^*(|V(H)|^{|V(G)})$ by a brute-force algorithm (the $O^*$-notation hides factors ...
8
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 Sgall in certain cases. The examples we use are complete bipartite graphs, where we used some extremal combinatorics to analyse them.
The work was motivated in ...
8
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 give an algorithm that, for every $k$ solves $k$-SAT in time $2^{n(1-\epsilon/2)}$.
Consider a $k$-SAT instance with $n$ variables, apply the sparsification lemma ...
8
I think for getting 1.99-approximation algorithm this paper by Manurangsi and Trevisan, has the current fastest algorithm.
7
A partial answer is that for even $k$ such a labeling does not exist.
For a set of $t$ disjoint subsets $S_1, \ldots, S_{t}$ (of size $n/k$, let $f(S_1, \ldots, S_t)$ denote the sum of their values).
Claim: if $t < k$ and $S_1 \cup \ldots \cup S_t \ne S'_1 \cup \ldots \cup S'_t$ then $f(S_1, \ldots, S_t) \ne f(S'_1, \ldots, S'_t)$.
To see why the claim ...
7
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$
$B \rightarrow a \mid aB \mid aBB$
$C \rightarrow a \mid aC \mid aCC$
How was it built:
I started from the grammar
$\{S \rightarrow S S \mid a\}$ which is ...
7
Permutational Isomorphism of Permutation Groups, aka Permutation Group Conjugacy:
Input: Two lists of permutations in $S_n$, say $(\pi_1, \dotsc, \pi_k)$ and $(\rho_1, \dotsc, \rho_\ell)$
Output: A permutation $\pi \in S_n$ such that $\pi^{-1} \langle \pi_1, \dotsc, \pi_k \rangle \pi = \langle \rho_1, \dotsc, \rho_\ell \rangle$, or "NOT ISOMORPHIC"
(...
7
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 need to provide a reduction from an intersection problem instance of size $n$ to a SAT instance of size $2\cdot log_2(n)$.
This kind of reduction would be ...
7
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 corresponds to a constraint $x_1 + x_3 + (1-x_4) + (1-x_6) \geq 1$, when all variables are forced to take values $0$ and $1$.
Hence if integer programming in $...
7
$\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}$ relative to any oracle, this should resolve 1. (I say "should" because I haven't checked all the details...)
*UP-generic oracles are discussed, for example, by ...
7
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=EXP}$ (which, together with the first equality, actually implies $\mathrm{EXP=ZPP}$).
6
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]. Even for the restricted one-page crossing number, in which the vertices are placed on the boundary of a disk and the edges interior to the disk, known ...
6
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 decomposition). Assuming SETH, they show that the constant $2+\sqrt{2}$ cannot be improved.
Thus their results give a $(2+\sqrt{2})^n n^{O(1)}$ algorithm, and their ...
6
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 planar graphs have treewidth $O(\sqrt{n})$.
In this problem we are given a graph with integer capacities on the vertices. We are asked to select a minimum ...
Only top voted, non community-wiki answers of a minimum length are eligible
