28
If $\mathsf{NP} = \mathsf{PSPACE}$, this would imply:
$\mathsf{P^{\#P}} = \mathsf{NP}$That is, counting the solutions to a problem in $\mathsf{NP}$ would be polytime reducible to finding a single solution;
$\mathsf{PP} = \mathsf{NP}$That is, polynomial-time randomized algorithms with success probability arbitrarily close to 1/2 is polynomial-time reducible ...
27
$
\newcommand{\DSPACE}{\mathsf{DSPACE}}
\newcommand{\L}{\mathsf{L}}
\newcommand{\P}{\mathsf{P}}
\newcommand{\DTIME}{\mathsf{DTIME}}
$
$\L^2 \subseteq \P$ would refute the Exponential Time Hypothesis.
If $\L^2 \subseteq \P$
then by a padding argument
$\DSPACE(n) \subseteq \DTIME(2^{O(\sqrt n)})$.
This means that the satisfiability problem $\mathsf{SAT} \...
26
The following is an obvious consequence:
$\mathsf{L}^{1+\epsilon} \subseteq \mathsf{P}$ would imply $\mathsf{L} \subsetneq \mathsf{P}$ and therefore $\mathsf{L} \neq \mathsf{P}$.
By the space hierarchy theorem, $\forall \epsilon > 0: \mathsf{L} \subsetneq \mathsf{L}^{1+\epsilon}$ .
If $\mathsf{L}^{1+\epsilon} \subseteq \mathsf{P}$ then $\mathsf{L} \...
23
One point which has been implicitly but not explicitly mentioned yet is that we would get $\mathsf{NP} = \mathsf{coNP}$. Although this is equivalent to $\mathsf{PH}$ collapsing to $\mathsf{NP}$, it follows directly from the fact that $\mathsf{PSPACE}$ is closed under complement, which is trivial to prove.
I think $\mathsf{NP} = \mathsf{coNP}$ is worth ...
20
$\mathsf{PH}$ collapses. A $\mathsf{PSPACE}$-complete problem must be in some level of $\mathsf{PH}$, say it's in $\mathsf{\Sigma_k P}$. Since it's $\mathsf{PSPACE}$-complete$=\mathsf{PH}$-complete (by assumption), $\mathsf{PH} \subseteq \mathsf{\Sigma_k P}$.
19
This is open, as far as I know. It could be provable (because its hypothesis may be false) or it just be difficult to show that any $2^{n^k}$-time algorithm for Succinct3SAT can be converted into a $2^{O(n)}$-time algorithm for Succinct3SAT.
In general, theorems of this kind are called "downward collapses" which say if two "large" classes are equal then two ...
19
It would still imply major separations of complexity classes. For example, $\mathrm{LOGSPACE \neq NP}$ would follow. (If $\mathrm{LOGSPACE = NP}$ then $\mathrm{LOGSPACE = PH}$.)
Also $\mathrm{NP \subseteq P/poly}$ would imply $\mathrm{PSPACE = \Sigma_2 P}$ by Karp-Lipton. It follows that $\mathrm{NP}$ has polysize circuits if and only if $\mathrm{PSPACE}$ ...
16
To me, one of the most basic and surprising consequences of $\mathsf{NP}=\mathsf{coNP}$ is the existence of short proofs for a whole host of problems where it is very difficult to see why they should have short proofs. (This is sort of taking a step back from "What other complexity implications does this collapse have?" to "What are the very basic, down-to-...
14
Honestly speaking, I do not think that Stack Exchange is a suitable place to ask for a future prediction. Despite this, I will post a response because it is fun to play with the idea of fortune telling.
As far as I know, the possibility of P≠RP=NP has not been ruled out. Moreover, there is a language A such that RPA=EXPA [Hel83, Kur83], which immediately ...
14
I'd say we have no good reason to think BQP is in P/poly. We do have reasons to think that BQP is not in P/poly, but they're more-or-less identical to our reasons to think that BQP≠BPP. E.g., if BQP⊂P/poly then Factoring is in P/poly, which is enough to break lots of cryptography according to standard security definitions.
Also, as you correctly ...
14
Here's another example from graph theory. The graph minor theorem tells us that, for every class $\mathcal{G}$ of undirected graphs that is closed under minors, there is a finite obstruction set $\mathcal{Obs(G)}$ such that a graph is in $\mathcal{G}$ if and only if it does not contain a graph in $\mathcal{Obs(G)}$ as a minor. However, the graph minor ...
13
In terms of complexity reasons (rather than complete problems): The Hartmanis-Immerman-Sewelson Theorem should also work in this context, namely: $\mathsf{EXP} \neq \oplus \mathsf{EXP}$ iff there is a polynomially sparse set in $\oplus \mathsf{P} \backslash \mathsf{P}$. Given how far apart we think $\mathsf{P}$ and $\oplus \mathsf{P}$ are - e.g. Toda showed ...
12
If ${\bf NP} = {\bf PSPACE}$
1) Polynomial Hierarchy would collapse to ${\bf NP }$.
2) We will now have that ${\bf NP } \not ={\bf NL}$ since we know that ${\bf PSPACE} \not = {\bf NL}$
---UPDATE---
3) It is known that ${\bf NL} \subseteq {\bf C_=L} \subseteq {\bf PL}$, where they are the logarithmic space bounded versions of ${\bf NP}$, ${\bf C_=P}$ and ...
11
If we also assume $\mathsf{NP}=\mathsf{RP}$, then the hypothesis would also cause the collapse of randomized classes: $\,\,\mathsf{ZPP}=\mathsf{RP}=\mathsf{CoRP}=\mathsf{BPP}$. Although these are all conjectured to unconditionally collapse into $\mathsf{P}$, anyway, it is still open whether that indeed happens. In any case, $\mathsf{NP}=co\mathsf{NP}$ does ...
11
“Berman-Hartmanis Conjecture Separates NP From All Super-Poly. DTIME Classes” — Worthy of arXiv.org?
I'm glad you are interested in complexity but there are some issues in your paper. Your techniques relativize and there is an oracle relative to which the Berman-Hartmanis conjecture is true and NP = EXP.
The main issue is that you can't do self-reference for time-bounded machines since you can't simulate and stay within the time bound.
10
In addition to the results pointed in all other answers, there is a one involving Interactive Proof Systems (${\bf IP}$), that are the generalization ${\bf NP}
$ where Verifier and Prover exchange messages in order to recognize a language.
It is known that ${\bf IP = PSPACE}$, so if ${\bf NP = PSPACE}$, it means that only one message is sufficient! For me ...
10
Emil Jeřábek' comment answers the question:
P/poly $=$ NP/poly is equivalent to NP $\subseteq$ P/poly
Note the corollary
P/poly $\neq$ NP/poly implies P $\neq$ NP.
Proof of corollary:
P/poly $=$ NP/poly is equivalent to NP $\subseteq$ P/poly $\ $ (Emil's comment)
NP $\subseteq$ P/poly implies P/poly $=$ NP/poly $\ $ (implied by 1.)
P/poly $\neq$ NP/...
8
Group isomorphism (with groups given as multiplication tables) would be in P. Lipton, Snyder, and Zalcstein showed this problem is in $\mathsf{L}^2$, but it is still open whether it is in P. The best current upper bound is $n^{O(\log n)}$-time, and because it reduces to graph isomorphism, stands as a significant obstacle to putting graph iso into P.
Makes ...
8
(I guess no one ever answered this older question with the newer results; here you go:)
Assuming the existence of quasipolynomially-hard indistinguishability obfuscation and subexponentially-hard one-way functions, there are Nash equilibria that are hard to find (and thus, $\mathsf{PPAD}$ is hard): On the Cryptographic Hardness of Finding a Nash Equilibrium
...
8
The only known proper containment is still $L \subsetneq PSPACE$, though they are all widely believed to be different. All the rest are still wide-open.
The recent work on ``Fine-Grained Complexity", like the Edit Distance result of Backurs and Indyk, side-steps the fact that we can't prove proper containments, like $P\neq NP$. In particular, SETH is a ...
8
Since PIT is in $\mathsf{coRP}$, if there is no efficient derandomization then $\mathsf{P} \neq \mathsf{RP}$ (and, in particular, $\mathsf{P} \neq \mathsf{NP}$, but that's not so surprising, since we expect that to be true anyways). This also implies, of course, that $\mathsf{P} \neq \mathsf{BPP}$, so anything which implies $\mathsf{P} = \mathsf{BPP}$ ...
7
We have
$$\mathrm{PP^{NP}\subseteq PP^{ModPH}\subseteq P^{PP}},$$
thus by the assumption,
$$\mathrm{PP^{PP}\subseteq PP^{NP}\subseteq P^{PP}\subseteq P^{NP}\subseteq NP}$$
as under the assumption, NP closed under complement. This implies $\mathrm{CH=NP}$.
answered Oct 10 '17 at 7:58
Emil Jeřábek supports Monica
10.9k3 gold badges40 silver badges63 bronze badges
6
There are two definitions for counting classes beyond ${\bf \#P}$. One was defined by Valiant and the other one was defined by Toda.
${ \rm \underline {Valiant's-Definition:}}$ For any class $C$, define $\#C =\cup_{A\in C}(\#P)^{A}$, where $({\#P}^A)$ means the functions counting the accepting paths of nondeterministic polynomial-time Turing machines ...
6
From Russell Impagliazzo's comment:
As a way of formalizing
what languages are in $\mathsf{P}$ if $\mathsf{P}=\mathsf{NP}$,
Regan introduced the complexity class $\mathsf{H}$.
A language $L$ is in $\mathsf{H}$ if and only if $L$ is in $\mathsf{P}^O$
relative to every oracle $O$ so that $\mathsf{P}^O=\mathsf{NP}^O$.
Thus, $L$ is in $\mathsf{...
6
As suggested by Sasho, my answer to the question "Applications of TCS to classical mathematics?" follows:
In his paper Straight Line Programs and Torsion Points on Elliptic Curves, Qi Cheng relates Bürgisser's $L$-conjecture (a variant of Shub and Smale's $\tau$-conjecture¹) to the Torsion Theorem and to Masser's Theorem in the field of elliptic curves.
...
6
Here's an example: Computational complexity and informational asymmetry in financial products by Arora, Barak and Ge shows that it can be computationally intractable (ie NP-hard) to price derivatives correctly - they use densest subgraph as an embedded hard problem.
Along the same lines and much earlier is the famous paper by Bartholdi, Tovey, and Trick on ...
6
The difference between your definitions is that the clause width in $s_\omega$ is allowed to grow with the number of variables, while for $s_\infty$ it is arbitrarily large but constant.
It's a similar issue as PH vs PSPACE. If you take an arbitrary constant number of quantifier alterations you get the polynomial hierarchy, but if you allow the formula to ...
5
Even, Selman, and Yacobi conjectured that there does not exist a disjoint $NP$-pair $(A, B)$ such that all separators of $(A, B)$ are $ \le_T^p $-hard for $NP$. This conjecture implies that $UP \ne NP$.
S. Even, A. Selman, and J. Yacobi. The complexity of promise problems with applications to public-key cryptography. Information and Control, 61:159–173, ...
answered Jan 19 '14 at 1:13
Mohammad Al-Turkistany
19.3k4 gold badges51 silver badges133 bronze badges
5
You can use complexity theoretic conjectures to prove things about, e.g., the representation theory of the symmetric group (see this blog post). Roughly speaking, since the word problem of the symmetric group $S_{2^k}$ is coNP hard, $S_{2^k}$ cannot have a faithful (i.e., injective) representation of dimension any smaller than $2^{\delta k}$ unless SAT has ...
5
Theorem 3.1 of One-Way Permutations and Self-Witnessing Languages C. Homan and M. Thakur, Journal of Computer and System Sciences, 67(3):608-622, November 2003. [ as .pdf ] states that $P≠UP∩coUP$ if and only if ("worst-case") one-way permutations exist. Theorem 3.2 recalls 10 further hypotheses that have been shown to be equivalent to $P≠UP∩coUP$.
Also, ...
Only top voted, non community-wiki answers of a minimum length are eligible
