34
Probably not. What you are asking is whether NP $\subset$ P/poly. If this were true, then the polynomial hierarchy would collapse (this is the Karp–Lipton theorem), something that is widely believed not to happen.
29
Yes, this is known. It appears in one of the must-cite references on triangle finding...
Namely, Itai and Rodeh show in SICOMP 1978 how to find, in $O(n^2)$ time, a cycle in a graph that has at most one more edge than the minimum length cycle. (See the first three sentences of the abstract here: http://www.cs.technion.ac.il/~itai/publications/Algorithms/min-...
26
There has, in fact, been quite a lot of recent works on proving quasi-polynomial running time lower bound for computational problems, mostly based on the exponential time hypothesis. Here are some results for problems that I consider quite natural (all results below are conditional on ETH):
Aaronson, Impagliazzo and Moshkovitz [1] show a quasi-polynomial ...
23
Megiddo and Vishkin proved that Minimum dominating set in tournaments is in $QP$. They showed that tournament dominating set has P-time algorithm iff SAT has subexponential time algorithm. Therefore, tournament dominating set problem can not be in $P$ unless the ETH is false.
It is very interesting to note that the exponential time hypothesis simultaneously ...
answered Nov 14 '15 at 17:08
Mohammad Al-Turkistany
20.3k4 gold badges56 silver badges142 bronze badges
22
While admittedly I haven't done the analysis, and this is not strictly a decision problem, I am willing to wager the best known matrix multiplication algorithms (by Coppersmith, Winograd, Stothers, Williams, et al) have irrational exponent.
This can be seen more clearly in the simple case of Strassen's algorithm, which has running time $O(n^{\log_2 7})$.
...
20
This is still #P-complete [1]. This problem is usually referred to as montone (#)SAT. Monotone #2-SAT is already #P-complete (this is equivalent to counting vertex covers of a graph).
[1] Roth, Dan. "On the hardness of approximate reasoning." Artificial Intelligence 82.1-2 (1996): 273-302.
16
Visibly pushdown automata (or nested word automata, if you prefer working with nested words instead of finite words) extend the expressive power of deterministic finite automata: the class of regular languages is strictly contained within the class of visibly pushdown languages. For deterministic visibly pushdown automata, the language inclusion problem can ...
16
Treewidth is NP-hard to compute on co-bipartite graphs, indeed the original NP-hardness proof of treewidth of Arnborg et al. shows this. Additionally, Bodlaender and Thilikos showed that it is NP-hard to compute the treewidth of graphs of maximum degree $9$. Finally, for any graph of treewidth at least $2$, subdividing an edge (i.e, replacing the edge by a ...
15
The famous primality testing problem, shown to be in P in the 2000 paper PRIMES is in P.
15
There is a notion of a monotone non-deterministic and, more generally, alternating Turing machine in the paper Monotone Complexity by Grigni and Sipser. Since polynomial time is the same as alternating logarithmic space, a machine characterization of uniform $\mathsf{mP}$ is the monotone alternating logspace Turing machine. Providing such a machine with ...
14
If infinite words are in your scope, you can generalize DFA (with parity condition) to the so-called Good-for-Games automata (GFG), that still have polynomial containment.
A NFA is GFG if there is a strategy $\sigma:A^*\times Q\times A\to \Delta$, that given the prefix read so far and the current state and letter, chooses a transition to go to the next ...
14
This problem is Monotone-SAT. It is #P-Complete under Cook Reductions. It is one of those problems that are "easy to decide but hard to count." I recommend the following paper. Self-Reducibility of Hard Counting Problems
with Decision Version in P
14
Concerning Question 1, there have mainly been two lines of work to find tractable restrictions of SAT.
The first one that you are already familiar with is to restrict the types of the clauses that you are allowed to use. For example, in 2-SAT, you are only allowed to use size two clauses. In Horn-SAT, you only allow Horn clauses etc. The tractable ...
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.
13
It's not quadratic, but Alon Yuster and Zwick ("Finding and counting given length cycles", Algorithmica 1997) give an algorithm for finding triangles in time $O(m^{2\omega/(\omega+1)})$, where $\omega$ is the exponent for fast matrix multiplication. For 4-cycle-free graphs, plugging in $\omega<2.373$ and $m=O(n^{3/2})$ (else there is a $4$-cycle ...
13
Johnson graphs are actually easy to recognize. In particular, you can recognize whether an input graph is a Johnson graph in polynomial time, and you can construct an isomorphism between two isomorphic Johnson graphs in polynomial time.
Johnson graphs come into the proof in a different way. Very roughly speaking, the proof juggles between group-theoretic ...
12
Testing perfect graphs.
Famous people (Lovasz, Knuth, ...) conjectured in the 1980s that there is
a polynomial time recognition for perfect graphs. Such an algorithm was
found after almost 20 years later by famous people ( Cornuéjols and other, FOCS 2003).
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
The $k$-disjoint path problem for fixed $k$. Given an undirected graph $G$ and $k$ node pairs $s_1t_1,s_2t_2,\ldots,s_kt_k$, are there node-disjoint paths in $G$ connecting the pairs? Polynomial-time algorithm follows from the work of Robertson and Seymour and relies on very non-trivial and difficult graph theoretic results. There are more general problems ...
12
Group Isomorphism! Although Ricky Demer gave lots (though certainly not all) details on this, there is an important point I want to highlight, esp. given the stated motivation for the question, namely:
Putting Group Isomorphism into $\mathsf{P}$ is a key obstacle to putting Graph Isomorphism into $\mathsf{P}$
Group Isomorphism (when given by ...
12
If $\mathrm{P\subseteq CSL}$, then $\mathrm{P\subseteq DSPACE}(n^2)$. By a padding argument, this implies
$$\mathrm{DTIME}(t(n))\subseteq\mathrm{DSPACE}\bigl(t(n)^\epsilon\bigr)$$
for every superpolynomial well-behaved function $t(n)$ and every $\epsilon>0$. I believe such a strong advantage of space over time is not expected to be true. The best ...
11
A Non deterministic XOR automaton (NXA) fits your question.
A NXA $M$ is essentially an NFA, but a word $w\in \Sigma^*$ is said to be in $L(M)$ if it is accepted by an odd number of paths (Xor relation) instead of being accepted if there exists an accepting path for it (Or relation).
NXAs are used for creating small representations of regular languages as ...
11
With respect to Problem II, it is coNP-hard (under Karp reductions) to tell if the number of unreachable strings is 0 or at least $1 - 2^{-\text{poly}(|x|)}$ fraction of all strings. I suspect there is a way to boost this and show that the gap problem is PSPACE-hard, maybe by using IP as a robust characterization of PSPACE.
Let $L$ be a coNP-complete ...
11
Computing VC dimension seems unlikely to be in polynomial time, but has a quasipolynomial time algorithm.
Also, it seems hard to detect a planted clique of size $O(\log n)$ in a random graph, but one can be found in quasipolynomial time; though the nature of this promise problem is somewhat different than the others mentioned.
11
Yes, exactly what you suggested is true: if there is a sparse $\mathbf{P}$-complete set under log-space many-one reductions, then $\mathbf{P} = \mathbf{L}$. This was conjectured by Hartmanis in 1978 and proven by Cai and Sivakumar in 1995. See this paper.
Hartmanis also conjectured that if there is a sparse $\mathbf{NL}$-complete set under log-space many-...
10
Solving the planted clique problem of distinguishing a uniformly random graph from the union of a random graph and a clique (of size intermediate between $2\log_2 n$ and $\sqrt n$), with success probability bounded away from 1/2. It differs from your ETH-violating example of finding polylog-sized cliques in arbitrary graphs, because this is an average-case ...
9
You can decide if a quadratic polynomial $p: \mathbb{R}^n \rightarrow \mathbb{R}$ has real roots with some linear algebra. As you note, the general case should be hard.
Observe first that $p(x) \neq 0$ for all $x \in \mathbb{R}^n$ if either $p(x) > 0$ or $p(x) < 0$ for all $x$ (this follows by continuity). So it is enough to be able to decide if $p(x) ...
9
Yes. Time-bounded Kolmogorov complexity is at least one such "generalization" (though strictly speaking it's not a generalization, but a related concept). Fix a universal Turing machine $U$. The $t(n)$-time-bounded Kolmogorov complexity of a string $x$ given a string $y$ (relative to $U$), denoted $K^t_U(x | y)$ (the subscript $U$ is often supressed) is ...
9
One simple consequence is $\mathbf{P}/\text{poly} = \mathbf{L}/\text{poly}$. Proof: For any language $A \in \mathbf{P}/\text{poly}$, there is a language $B \in \mathbf{P}$ and a sequence of polynomial-length advice strings $y_1, y_2, y_3, \dots$ such that $x \in A \iff (x, y_{|x|}) \in B$. By assumption, there is a language $C \in \mathbf{L}$ and a sequence ...
Only top voted, non community-wiki answers of a minimum length are eligible
