Skip to main content
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
8 votes
Accepted

Complexity of permanent verification

At the very least, the problem is "hard for the polynomial hierarchy" in the following sense. Let $PermVerify$ be the problem specified. Then $$PH \subseteq P^{\#P} \subseteq NP^{PermVerify}$...
Ryan Williams's user avatar
8 votes
Accepted

Is there a well-defined notion of an “R/poly” complexity class?

There is nothing stopping you from defining the class, though I don’t recall seeing it studied. Actually, I can see two reasonable definitions for this class. The first one, which follows more ...
Emil Jeřábek's user avatar
8 votes
Accepted

Relation between ACC^0 and DTIME

Most people would believe that DTIME(n) contains problems that are not in non-uniform ACC^0 (poly size). One reason is that the containment of DTIME(n) in non-uniform ACC^0 implies P is contained in ...
Ryan Williams'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
Accepted

Problems where "maximal" is hard, but "maximum" is easy?

It’s not clear from the question how $\Sigma$ and $L$ may depend on the input. E.g., in the mentioned CLIQUE problem, we are given a graph $G=(V,E)$ as input, and we put $\Sigma=V$ and $L=\{C\subseteq ...
Emil Jeřábek'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

What is the probability a random language in $\mathsf{PSPACE}$ is in $\mathsf{P}$?

As pointed out by Emil, and I think maybe the OP already knew based on the last sentence of the OQ, there isn't actually a uniform distribution on a countable set. However, Jack Lutz developed the ...
Joshua Grochow'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
3 votes

Complexity results for Lower-Elementary Recursive Functions?

Since lower elementary functions are computable in time $2^{O(n)}$ (and space $O(n)$), the set of corresponding decision problems is unlikely to include NP, or even just $\mathrm{NTIME}(n^{1+\epsilon})...
Emil Jeřábek's user avatar
3 votes

Ruzzo-Simon-Tompa oracle access mechanism

In this paper https://people.cs.rutgers.edu/~allender/papers/pl3.pdf Mitsu Ogihara and I show that the "oracle" #L hierarchy (and related classes) with the Ruzzo-Simon-Tompa access mechanism ...
Eric Allender's user avatar
3 votes

Structural Complexity Theory References

Joshua Grochow gave a very detailed list in his answer. I would like to mention a few sources that present more introductory/intermediate material, although these may not be useful for OP (hopefully, ...
Cyriac Antony's user avatar
2 votes
Accepted

Where does a problem lie which is NP-hard but not QMA-hard?

Yes, an $NP$-hard problem high up in the polynomial hierarchy would likely not be $QMA$-hard, since otherwise $QMA$ would be contained in $PH$, exactly as you point out. In fact, we don't need to look ...
Lieuwe Vinkhuijzen's user avatar
2 votes

Is the protocol perfect zero knowledge?

Zero-knowledge proofs do not in general compose in parallel. See this paper by Feige and Shamir for a (contrived) counterexample. Beyond this counterexample, there are several constraints to actually ...
lamontap's user avatar
  • 1,010
2 votes

Problems where "maximal" is hard, but "maximum" is easy?

Lemma 1. There is a language $L$ (in this case a collection of sets, suitably encoded) such that the problem of deciding whether a given set $x$ is a maximal element of $L$ is NP-hard, while the ...
Neal Young's user avatar
  • 10.8k
2 votes

Is Parity-P contained in PP?

It says that $\oplus P \subseteq PP$ on page 293 in chapter "A Rogues' Gallery of Complexity Classes" of "The Complexity Theory Companion". However, they do not provide a reference ...
Tayfun Pay's user avatar
  • 2,618
1 vote
Accepted

Solve 3CNF in Poly-Time with Satisfiability Oracle

hint: assign values to variables one at a time and call algorithm A on resulting formula. if the result of algorithm A is satisfiable or non-satisfiable what does that mean about last variable ...
floating's user avatar
1 vote

Structural Complexity Theory References

Another quite comprehensive textbook that was not mentioned in the earlier answers is this: Theory of Computational Complexity, by Ding-Zhu Du and Ker-I Ko. Here is the Amazon link to the book: https:/...
Andras Farago's user avatar
1 vote
Accepted

Which 1-player games are EXPTIME-complete? Also, are there any known games that are EXPSPACE-complete?

From the comments, the desiderata are: Preferably, a game that is/was in play by some human population (as opposed to one whose rules were written to have it fall in the complexity class that I am ...
Kevin Wang's user avatar
1 vote
Accepted

Is modular square roots modulo primes in $NC$?

Square roots modulo $2^n$ can be computed in (uniform) $\mathrm{TC}^0$. More generally, just like in On parallel complexity of modular inverse, given $X$ and $M$ in binary and $b$ in unary such that $...
Emil Jeřábek's user avatar

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