86
Here is a further intuitive and unpretentious explanation along the lines of MGwynne's answer.
With $2$-SAT, you can only express implications of the form $a \Rightarrow b$, where $a$ and $b$ are literals. More precisely, every $2$-clause $l_1 \lor l_2$ can be understood as a pair of implications: $\lnot l_1 \Rightarrow l_2$ and $\lnot l_2 \Rightarrow l_1$. ...
33
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.
31
Consider resolution on a 2-SAT formula. Any resolvent is of size at most 2 (note that $n + m -2 \le 2$ if $n, m \le 2$ for clauses of length $n$ and $m$ resp). The number of clauses of size 2 is quadratic in the number of variables. Therefore, the resolution algorithm is in P.
Once you get to 3-SAT you can get bigger and bigger resolvents, so it all goes ...
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
I think that there is a fundamental underlying difficulty with the question you are asking here (and that you asked in your related question about incomprehensible languages).
Roughly speaking, it seems you're seeking a language $L$ such that
$L\in P$ but ZFC doesn't know that $L\in P$.
To understand the difficulties with your question, I think you must ...
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})$.
...
21
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 ...
20
As Walter says, clauses of 2-SAT have a special form. This can be exploited to find solutions quickly.
There are actually several classes of SAT instances that can be decided in polynomial time, and 2-SAT is just one of these tractable classes. There are three broad kinds of reasons for tractability:
(Structural tractability) Any class of SAT instances ...
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.
19
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
13.9k4 gold badges49 silver badges131 bronze badges
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
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 ...
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
The famous primality testing problem, shown to be in P in the 2000 paper PRIMES is in P.
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
13
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 ...
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
Take a formula $\phi$ in 3-CNF over variables $V=\{v_{i}\}$ and clauses $C=\{c_{j}\}$, and let $A:V\rightarrow \{TRUE,FALSE\}$ be an arbitrarily chosen assignment.
The clauses of $\phi$ can be divided into two categories, those that are satisfied by $A$ and those that aren't. All those that are satisfied have at least one literal that evaluates to $TRUE$, ...
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
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 ...
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
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 ...
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
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 ...
10
Ok, so you have a polygon $P$ with integer-length axis-parallel sides and possibly with holes (the shape you want to cover) and you want to partition it into as few $1\times a$ or $b\times 1$ rectangles as possible. At first I thought you wanted the minimum partition into rectangles of arbitrary shapes, which has a known polynomial time solution involving a ...
10
If you understand the algorithm for 2SAT, you already know why it's in P - this is precisely what the algorithm demonstrates. I think this comic illustrates my point. As you already know why 2SAT is in P, what you probably want to know is why 2SAT isn't NP-hard.
To understand why 2SAT isn't NP-hard, you have to consider how easy it is to reduce other ...
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 ...
Only top voted, non community-wiki answers of a minimum length are eligible
