Skip to main content
Share Your Experience: Take the 2024 Developer Survey
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 ...
Pasin Manurangsi's user avatar
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. "...
holf's user avatar
  • 2,174
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 ...
daniello's user avatar
  • 3,266
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 ...
holf's user avatar
  • 2,174
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 ...
Tayfun Pay's user avatar
  • 2,598
14 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 ...
a3nm's user avatar
  • 9,419
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 ...
Yuval Filmus's user avatar
  • 14.5k
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 ...
Emil Jeřábek's user avatar
11 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 ...
Peter Shor 's user avatar
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 ...
Joe Bebel's user avatar
  • 2,295
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 ...
William Hoza's user avatar
  • 1,743
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-...
William Hoza's user avatar
  • 1,743
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 ...
Lijie Chen's user avatar
9 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 ...
Eric Allender's user avatar
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 ...
Shaull's user avatar
  • 5,646
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 ...
Sariel Har-Peled's user avatar
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 ...
Gamow's user avatar
  • 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-...
David Eppstein's user avatar
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 ...
Eric Allender's user avatar
7 votes

Non-Orthogonal Vectors Problem

If $k=O(\log n)$ I believe the techniques of Alman, Chan, and Williams give the best known solution to the Non-Orthogonal Vectors Problem. (They phrase it differently, as a Hamming closest pair ...
Rasmus Pagh's user avatar
7 votes
Accepted

Why is the "general notion of a reduction [...] inherent to the notion of self-reducibility"?

I think you may be misunderstanding the sentence "Note that the general notion of a reduction (i.e., Cook-reduction) seems inherent." This is not about reductions being inherent to self-reducibility (...
Sasho Nikolov's user avatar
7 votes

Solving 3-SAT in O(n^6)?

You can find all weird stuff out there... For example, just google "graph isomorphism problem 2022", and the first search result is this polytime algorithm... https://www.biorxiv.org/content/...
Avi Tal's user avatar
  • 1,606
7 votes
Accepted

Running time analysis of problems with a variable in problem definition

You seem to be studying the parameterized complexity of the problem. This is a branch of Complexity Theory where you add a parameter, which is part of the input but is seen as a separate value. For ...
alsips-cl's user avatar
  • 158
6 votes
Accepted

On complexity of linear programming with quadratic equality/inequality constraints?

A famous result by Motzkin and Straus expresses the $k$-clique problem as the maximization of a quadratic function subject to a system of linear constraints. In particular, they prove: Let $G$ be ...
Gamow's user avatar
  • 5,772
6 votes

Can we recover integers $a_i$ from the sum $a_0 + a_1e+a_2e^2+\cdots+a_ne^n$?

This is impossible. No finite number of bits of $f(a_0,\dots,a_n)$ suffices to determine any of $a_0,\dots,a_n$; in fact, any nondegenerate real interval contains the values $f(a_0,\dots,a_n)$ for ...
Emil Jeřábek's user avatar
6 votes
Accepted

What are the consequences of $BPP \neq P$?

To me, the intuitive reason for believing that $BPP = P$ is that if you describe to me a randomized algorithm, then in practice, I can implement it by using a pseudorandom number generator (PRNG) ...
Timothy Chow's user avatar
  • 7,550
5 votes
Accepted

Complexity of counting integer roots of multivariate polynomials in a polyhedron?

The decision version of this problem is obviously in $\mathsf{NP}$, and Manders & Adleman showed that a specific case is NP-complete. Namely, even deciding whether there exists an integer $x \in [...
Joshua Grochow's user avatar
5 votes

Is there a polynomial time algorithm to determine if the span of a set of matrices contains a permutation matrix?

Theorem. The problem in the post is NP-hard, by reduction from Subset-Sum. Of course it follows that the problem is unlikely to have a poly-time algorithm as requested by op. Here is the intuition. ...
Neal Young's user avatar
  • 10.8k
5 votes

On integer programming

It's NP-hard. Given an integer programming problem $P$, add an irrelevant variable $z$ with no constraints; call the resulting problem $P'$. Now if $P$ has no solutions, then $P'$ has no solutions; ...
D.W.'s user avatar
  • 12.1k

Only top scored, non community-wiki answers of a minimum length are eligible