29
votes
Accepted
Given a 4-cycle free graph $G$, can we determine if it has a 3-cycle in quadratic time?
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 ...
- 27.3k
26
votes
Is there a natural problem in quasi-polynomial time, but not in polynomial time?
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 ...
- 306
24
votes
Is there a natural problem in quasi-polynomial time, but not in polynomial time?
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, ...
- 20.8k
21
votes
Accepted
Time complexity with irrational exponent?
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, ...
- 2,295
20
votes
Accepted
Counting the number of satisfying assignments in a POSITIVE CNF-SAT
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. "...
- 2,164
18
votes
Are there interesting graph classes where the treewidth is hard (easy) to compute?
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 ...
- 3,256
16
votes
Accepted
On theoretical aproaches for solving $\mathsf{SAT}$ in special cases
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 ...
- 2,164
15
votes
Counting the number of satisfying assignments in a POSITIVE CNF-SAT
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 ...
- 2,579
13
votes
Given a 4-cycle free graph $G$, can we determine if it has a 3-cycle in quadratic time?
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$...
- 50.9k
13
votes
Accepted
questions on implications Babais quasi P time graph isomorphism result
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 ...
- 14.3k
13
votes
Accepted
Complexity of 1-or-3-in-3-SAT (odd-3-SAT)
Somewhat surprisingly to me, this problem is in fact in PTIME.
The key insight is that, considering a clause $C$, letting $0 \leq k \leq 3$ be the number of negated literals in $C$, then the clause is ...
- 8,896
12
votes
Accepted
What is the conjectured relationship between P (PTime) and Type 1 (context-sensitive) languages?
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 ...
- 16.9k
12
votes
Problems in quasi-polynomial time that could conceivably be in P (without causing collapses or violating widely held beliefs)
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:...
- 36.9k
11
votes
Is there a natural problem in quasi-polynomial time, but not in polynomial time?
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 ...
- 2,295
11
votes
Problems in quasi-polynomial time that could conceivably be in P (without causing collapses or violating widely held beliefs)
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 ...
- 50.9k
11
votes
Accepted
On sparse complete sets and P vs L
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 ...
- 1,733
10
votes
Choosing random permutations in "strict" polynomial time
If the only randomness you can obtain is sampling from a set of polynomial size, you are not going to be able to get two random permutations, because the probability of any particular pair of random ...
- 24.3k
9
votes
Accepted
What are the consequences of $P \subseteq L/poly$?
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-...
- 1,733
9
votes
Non-Orthogonal Vectors Problem
When $k$ is given as part of the input, the second problem is equivalent to the monochromatic Max-IP problem (given $S \subseteq \{0,1\}^d$, find $\max_{(a,b) \in S, a\ne b} a \cdot b$).
Recently I ...
- 176
8
votes
Problems in quasi-polynomial time that could conceivably be in P (without causing collapses or violating widely held beliefs)
Approximating the Directed Steiner tree problem to within a poly-logarithmic factor. Currently there is a quasi-polynomial time algorithm that gives an $O(\log^3 k)$-approximation. More precisely, one ...
- 6,979
8
votes
Is there a natural problem in quasi-polynomial time, but not in polynomial time?
If the exponential time hypothesis is correct (or even weaker versions), then one can not solve 3SAT for instances with polyglog number of variables in polynomial time. Of course, quasi-polynomial ...
- 9,596
8
votes
Is there a natural problem in quasi-polynomial time, but not in polynomial time?
Solving Parity games has recently been shown to be in QP:
https://www.comp.nus.edu.sg/~sanjay/paritygame.pdf
Parity games arise naturally in many formal verification contexts, such as LTL synthesis ...
- 5,531
8
votes
Accepted
Is Circuit Minimization $P$-hard under logspace reductions?
The Circuit Minimization Problem you describe is also known as MCSP (the Minimum Circuit Size Problem), which has been the subject of quite a few papers recently. (I'm posting an answer to this ...
- 1,761
8
votes
"Relatives" of the shortest path problem
Here is an answer to the first problem:
Path with minimum weight gap: find an $s-t$ path, such that the difference between the largest and smallest edge weights on the path is minimum.
A paper ...
- 5,772
8
votes
Accepted
6-regular graph without small 3-regular subgraph
6-regular Ramanujan graphs have girth (shortest cycle length) $\Omega(\log n)$, which means that their smallest 3-regular subgraphs do as well. However, the Moore bound on cages implies that every 3-...
- 50.9k
8
votes
Accepted
Fast algorithms for time bounded Kolmogorov complexity
TL;DR: It is believed that no polynomial time algorithm exists for neither $K_t$, $K^{poly}$ nor $KT$.
We have no idea about $K^{t^{\prime}}$ since it has never really been studied.
No faster ...
- 1,761
7
votes
Polynomial-time reductions between undecidable languages
Gödel's incompleteness theorem can be thought of as a reduction from the Halting problem to the language $\langle \varphi \mid \varphi \text{ is a true sentence in number theory}\rangle$, and a ...
- 2,295
7
votes
Accepted
Two extremely naive questions about the Kronecker problem from Geometric Complexity Theory
A) The input here is the triple of partitions $(\lambda, \mu, \nu)$, represented as sequences of numbers in binary. The dimension of the irreducible representation $M_{\lambda}$ can actually be ...
- 632
Only top scored, non community-wiki answers of a minimum length are eligible