25 votes

Theoretical Computer Science vs other Sciences?

As a theoretical computer scientist I am proud of the following achievements of the field. Logicians figured out that all logical connectives can be build from a single one, paving the road for ...
Andrej Bauer's user avatar
  • 28.8k
22 votes
Accepted

Why is the "balanced vs constant function" problem not a proof that P ≠ BPP?

It is true that if the function $f$ is given by an oracle, then a randomized algorithm is exponentially faster than any deterministic algorithm. With an oracle function, however, this is not a $BPP$ ...
Andras Farago's user avatar
18 votes

Theoretical Computer Science vs other Sciences?

As a TCS researcher, I understand the feeling and feel it too sometimes. I think it is healthy to be able to appreciate the wonder that other sciences have to offer. We must also keep in mind that it ...
Denis's user avatar
  • 8,678
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
15 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
14 votes

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
13 votes

What is the general consensus on the NL vs P question?

As far as I know, the general consensus is that NLOGSPACE (NL) is different from P. Indeed, it is believed that "Nick's Class" NC (which contains NLOGSPACE) is different from P. The main ...
Ryan Williams's user avatar
13 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
11 votes

Theoretical Computer Science vs other Sciences?

I run a small software business producing XML processing tools, so I'm very much a practical engineer rather than a theoretician. It's 50 years since I did my CS degree. And you know, I'm constantly ...
Michael Kay's user avatar
10 votes

Theoretical Computer Science vs other Sciences?

My impression from your comments is that perhaps you have just not seen enough theoretical CS to get to some of the kind of content you are excited about in, say, physics. I'll also point out that you ...
Joshua Grochow'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
Accepted

Complexity class of optimization problems whose fractional relaxation is polynomial-time solvable

The answer to the second question is no. Here is an example when the integer-output optimization problem is polynomial-time solvable, yet its fractional relaxation is NP-complete: In complements of ...
Andras Farago's user avatar
8 votes

General collection with the current state of complexity bounds of well-known unsolved problems?

For job scheduling problems, there is this complexity wiki. I am not sure if it is actively being updated.
Inuyasha Yagami'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
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
7 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
7 votes

Problems in NP with non-trivial certificate

I feel like problems $P\in\mathsf{NP}\cap\mathsf{coNP}$ are good examples for your question. Typically, for $P\not\in\mathsf{P}$, at least one of the witnesses is non-trivial. For example, the closest ...
Mark's user avatar
  • 948
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
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

What are the #P-complete subfamilies of #2-SAT?

Despite being 11 years late I hope I can still claim the bonus points! There is an (IMHO) simple and direct reduction from #SAT to #BIPARTITE-2SAT that does not rely on monotone instances. This ...
Tuomas Laakkonen's user avatar
6 votes

Priority queue implementation with both find-min and delete-min $o(\log n)$

It is trivial to build a heap where insert takes $O(n)$ time and find-min and delete-min take $O(1)$ time: simply store all the numbers in a linked list in sorted order. It is not possible to build a ...
D.W.'s user avatar
  • 12k
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

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.1k
5 votes

Problems in NP with non-trivial certificate

Kuperberg's certificate of knottedness of a knot is not entirely trivial, and (I believe still) contingent on the Generalized Riemann Hypothesis. It includes lots of not super-difficult, but not ...
Mark S's user avatar
  • 1,083
5 votes
Accepted

Example of a problem in $P^{PP}$?

For a simple problem in $\mathrm{P^{PP}}$ that’s presumably not in $\mathrm{PP}$: given a 3CNF $\phi$ in $n$ variables, determine the $\lfloor n/2\rfloor$-th bit of $|\{\vec a\in\{0,1\}^n:\phi(\vec a)=...
Emil Jeřábek'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
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
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

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

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