17
Graph Isomorphism is known to be in quasipolynomial time but not known to be in polynomial time: https://arxiv.org/abs/1512.03547
You can also come up with synthetic problems by the time hierarchy theorem, which essentially states that there are problems at any (deterministic) time complexity but not below: https://en.wikipedia.org/wiki/...
15
VC-dimension of set systems is known to be quasipolynomial but not known to be polynomial, with some evidence (based on the strong exponential time hypothesis) that it is not polynomial.
See:
Linial, Nathan, Mansour, Yishay, and Rivest, Ronald L. (1991), “Results on learnability and the Vapnik–Chervonenkis dimension”, Inf. Comput. 90 (1): 33–49.
Manurangsi, ...
10
Minimum dominating set in tournaments problem has quasi-polynomial time algorithm (hence sub-exponential). There is no known polynomial time algorithm for it. Tournament dominating set has polynomial-time algorithm if and only if SAT has sub-exponential time algorithm. Therefore, the exponential time hypothesis (ETH) implies that tournament dominating set ...
9
EDIT: Added Lemma 2 which covers all cases asked about.
Lemma 1. Given a DFA with alphabet $\{0,1\}$ and an integer $n$, it is possible to enumerate all length-$n$ words in the language of the DFA, in order of non-decreasing number of 1's, with the time taken between each word and the next polynomial in $n$ and the size of the DFA.
Proof. Here's the ...
9
Parity games have recently been shown to be solvable in quasipolynomial time: https://doi.org/10.1137/17M1145288
5
Really nice question(s). I don't fully follow Denis’ answer, so I'm going to try my own.
For question 1, I’m going to assume that you are familiar with Kolmogorov complexity (otherwise I could write a proof heavily using Kleene’s fixed point theorem, but such proofs tend to look like black magic, while Kolmogorov complexity is rather natural). Assume for the ...
3
Here is a negative answer to question 1.
Let us assume that there is a computable function $f$ such that there is a Turing machine $M$ recognizing $H$ in time $f(n)$ with oracle $\Gamma_{BB}$.
Let $g$ be a computable function bounding the maximal integer that $M$ can write on its tape on input of size $n$, for instance with binary encoding $g(n)=2^{f(n)}$.
...
2
Factoring integers
The General Number Field Sieve is known to be sub-exponential in the size of the input, for example see this quote from the link I just gave:
The running time of the number field sieve is super-polynomial but
sub-exponential in the size of the input.
However no polynomial-time algorithm for factoring integers is known (yet).
1
Discrete log in multiplicative groups of finite fields of small characteristic has quasi-polynomial running time. Specifically, for $\mathbb{F}_{p^n}^\times$ (where inputs have size $\log_2(p^n) = n\log_2(p)$) the (expected) running time is $(pn)^{2\log_2(n) + O(1)} = 2^{2\log_2(p)\log_2(n) + O(1) + 2 \log_2(n)^2 + O(\log_2(n))} = 2^{O(\log_2(n)^2)}$
1
OK, I'm coming back to this after some more thought based on the ideas of @GaraPruesse and @ChandraChekuri. I'm not 100% sure, because these arguments are a pain to formalize and visualize, but I think my problem of enumeration with special vertices coming in even groups (or in multiple-of-k groups) is in fact polynomially equivalent to the problem of two ...
1
Given a SAT clause of literals x1 or x2 or ... or xn, we can replace out 2 literals a, b as follows.
Introduce a new variable, c.
Let:
c <=> (a or b)
Replace a or b in the clause with c. The resulting clause has one less literal.
We need to convert that into CNF. First break that up into these two clauses:
c => (a or b)
(a or b) => c
Now ...
Only top voted, non community-wiki answers of a minimum length are eligible
