Skip to main content
2 votes

On the power of QMA(2)

The inclusion $EXP\subseteq QMA(2)$ is not known, and in fact is not expected to hold. It would imply that any exponential-size computation could be verified in polynomial time. In fact, the inclusion ...
Lieuwe Vinkhuijzen'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

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

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