Skip to main content
18 votes
Accepted

Is relation between BQP and QMA resolved?

I haven't looked at the paper carefully, but one thing I noticed is that their proof that BQP $\subsetneqq$ QMA works by their claiming that "bit commitment $\not \in$ BQP" but "bit ...
Peter Shor 's user avatar
16 votes
Accepted

Status of András Faragó’s (second) claimed proof that NP=RP

It seems to me that Theorem 1 in the paper is false for essentially the same reasons as the Peres example showed in the last version. Theorem 1 seems to say the following, at least in a special case. ...
Jason Gaitonde's user avatar
15 votes
Accepted

Problems that are NP-Complete when restricted to graphs of treewidth 2 but polynomial on trees

L(2,1)-labeling is such a problem. The input is (just) a graph and we want to color it using the minimum number of colors so that neighboring vertices have colors that differ by at least 2 and ...
Michael Lampis's user avatar
14 votes
Accepted

Structural Complexity Theory References

I don't think there really are canonical references for this stuff (roughly: advanced modern structural complexity theory), but here are some references. This list is partially geared towards my ...
Joshua Grochow's user avatar
13 votes
Accepted

Law of the Excluded Middle in complexity theory

There are several other non-constructive arguments that work along similar Karp-Lipton-esque lines, such as Santhanam's proof (STOC 2009) that $PromiseMA$ is not in $SIZE(n^k)$ for some $k$, and ...
Ryan Williams's user avatar
12 votes
Accepted

How stringent is the peer review process of ECCC exactly?

ECCC is supposed to reject any paper that is submitted without something that appears to be a proof for all of the main theorems. There is no expectation that a board member is going to check that ...
Eric Allender's user avatar
10 votes
Accepted

Trade-off for Barrington's theorem

Perhaps what you're looking for is theorem 2 in Cleve, R. Towards optimal simulations of formulas by bounded-width programs. I don't think the precise statement that you're asking about is known (note ...
Ryan Williams's user avatar
8 votes

Does $NC=P$ imply the collapse of Polynomial Hierarchy?

It appears that nobody has provided an answer to this question. One reason may be that it's not clear what you mean by "the rest of the polynomial hierarchy". Indeed, it's not clear that P=...
Eric Allender's user avatar
8 votes
Accepted

What can we do with a generic oracle (as opposed to a random one)?

In fact, GenericallyP = P: Proposition. The following are equivalent for any language $L$: $L\in\mathbf P$. $L\in\mathbf{GenericallyP}$. $\{A\in\{0,1\}^\mathbb N:L\in\mathbf P^A\}$ is not meager. ...
Emil Jeřábek's user avatar
8 votes
Accepted

A contradiction in the realm of quantum digital and analog computation

Blum-Shub-Smale machines manage to solve NP-complete problems by using an exponential number of the digits of precision. Nothing that you can do in a physics experiment uses more than thirty digits of ...
Peter Shor 's user avatar
7 votes
Accepted

Approaches to fast matrix multiplication and their limits

Their phrase in that paper "All work on matrix multiplication since 1986" is...an oversimplification. While it's true that what they cite are all the papers that have improved the state of ...
Joshua Grochow's user avatar
6 votes

Are there any problems in $\mathsf{BPP}$ that are known to be $\mathsf{RP}$-hard or $\mathsf{coRP}$-hard?

It would be a very interesting result if one were able to present a language in BPP that is hard for RP (equivalently, for co-RP) under poly-time Turing reducibility (aka Cook reducibility). I'm ...
Eric Allender's user avatar
6 votes
Accepted

Is P=NP relative to the halting oracle?

$\text{P}^\mathcal{H} = \text{NP}^\mathcal{H} = \text{PSPACE}^\mathcal{H}$ as noted in the linked answer (note that the query tape counts as space). Specifically, using $n$ calls to the halting ...
Dmytro Taranovsky's user avatar
6 votes
Accepted

$\mathsf{TC^0}$-completeness and reductions

For question #1: If there is a complete problem for uniform TC$^0$ under uniform AC$^0$ m-reductions, then the counting hierarchy collapses. I don't know if this qualifies as "bad". For ...
Eric Allender's user avatar
6 votes

Resource-bounded variant of Kolmogorov complexity

The question was revised (in the comments) to ask: Given x, output the shortest description d such that U(d) = x in time $|d|^2$. Yanyi Liu and Rafael Pass showed (in FOCS 2020) that this function is ...
Eric Allender's user avatar
6 votes

How does one "understand" complexity theory?

It's a nice question, but before partially answering it I want to question part of the premise. My main thesis here is that all mathematical fields are actually just loosely coherent collections of &...
Joshua Grochow's user avatar
6 votes
Accepted

Complexity of determining whether the language of an P machine is empty

It's equivalent (under Turing reduction) to deciding whether the language of any given TM is empty. That is, it is co-RE-complete. This can be shown using a standard padding argument. Here are the ...
Neal Young's user avatar
  • 10.8k
6 votes
Accepted

Intersection Non-Emptiness for Two-Way Finite Automata

Unlike one-way models, intersection of 2-way NFAs is "cheap": Given 2-way NFAs $A_1,A_2$, you can construct a 2-way NFA $B$ for their intersection that works as follows: it first behaves ...
Shaull's user avatar
  • 5,656
6 votes
Accepted

How to prove that a problem is not smoothed-polynomial?

With respect to smoothed analysis, the only case that I am aware of is the paper by Beier and Vöcking (Typical Properties of Winners and Losers in Discrete Optimization. SIAM J. Comput. 35(4): 855-881,...
Bodo Manthey's user avatar
5 votes

Functions with polytime iterated applications

It can be done whenever $f$ is linear (over any semiring), by representing it as a matrix and using matrix exponentiation. If it can be done for $f$, it can be done for $f$ conjugated by any $FP$ ...
Command Master's user avatar
5 votes

Bijection between NP-complete problems

To expand on Bruno and Emil's comments, the Berman-Hartmanis isomorphism theorem [1, p.312] says yes, provided $A$ and $B$ are paddable: If both $A$ and $B$ are paddable, there exists a polynomial-...
Neal Young's user avatar
  • 10.8k
5 votes
Accepted

Deciding finiteness of regular language is NL-complete?

Let $\mathcal{A}$ be an NFA. We say that a state $q$ lies on a cycle if there is a non-empty path from $q$ to $q$ in the graph of $\mathcal{A}$. In my answer I assume that the following lemma is true: ...
Bartosz Bednarczyk's user avatar
5 votes
Accepted

Complexity of analytic functions and integrals

You cannot compute such functions "in P", or in any conventional complexity class for that matter, for the fundamenal reason that their inputs and outputs are real numbers that cannot be ...
Emil Jeřábek's user avatar
5 votes

Law of the Excluded Middle in complexity theory

I finally managed to track down the paper that I was struggling to recall. Why are Proof Complexity Lower Bounds Hard? by Ján Pich and Rahul Santhanam, FOCS 2019. Their main result is: Theorem 1. ...
Timothy Chow's user avatar
  • 7,560
4 votes
Accepted

Intuition on Lupanov's Upper Bound on Circuit Size

Yes, there is a simpler construction, essentially due to Shannon. For every $k$, all $2^{2^k}$ functions on $k$ variables can be implemented by a circuit of size $2^{2^k}$ (just take some ...
Vladimir Lysikov's user avatar
4 votes
Accepted

Complexity of maximum k-edge-colorable subgraph of a bipartite graph

A bipartite multigraph is $k$-edge colorable iff the maximum degree of any vertex is at most $k$. So we are asking for a subgraph $H=(V,F)$ of a given bipartite graph $G=(V,E)$ such that $\delta_H(v) \...
Chandra Chekuri's user avatar
4 votes

Problems complete for non-deterministic PSPACE

A class that was more familiar at the time than NPSPACE was the class of context-sensitive languages. Let CSL denote the set of context-sensitive languages. By Kuroda's theorem (1960), this set is ...
Hermann Gruber's user avatar
4 votes

Complexity of simplex method

It could be that the variants refer to two different forms of Linear Programs. Simplex only works with problems in Standard Equality Form (SEF) which is of the form $$\min c^T x\,\,\,\,\text{s.t.}\,\,\...
NaturalLogZ's user avatar
4 votes

Problems that are NP-Complete when restricted to graphs of treewidth 2 but polynomial on trees

Another problem is Minimum Sum Edge Coloring. The input is a graph and the task is to compute a proper edge-coloring $\chi: E\to \mathbb{N}$ such that $\sum_{e\in E} \chi(e)$ is minimal. Here, proper ...
Christian Komusiewicz's user avatar
4 votes

Reference request: finite field computation over the Word-RAM model

Looks like Lemma 2.6 from https://arxiv.org/abs/2403.20326 answers my question. Constant time addition and multiplication are possible over $\mathbb{F}_q$ in the Word-RAM model, provided you first ...
Naysh's user avatar
  • 686

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