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} \...
27
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 ...
22
$\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}$.
20
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}$ ...
18
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
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 ...
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 ...
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 ...
12
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 ...
12
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/...
11
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 ...
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
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
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
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 ...
7
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 ...
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}$.
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 ...
5
A better way to define these exponents is if you ask about the running time in the form $c^n\cdot poly(|F|)$, where $poly(|F|)$ is an arbitrary polynomial of the input size. Then artifacts like the $3^v$ size disappear.
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
20.4k4 gold badges57 silver badges144 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, ...
5
As I wrote in my answer to the other question
let's make the argument constructive and uniform in the number of alternations
by giving an algorithm that solves $\Sigma^P_k$ assuming that
we have a polynomial-time algorithm for SAT and
see what we would get if $k$ is not constant.
Let $M$ be a DTM with two inputs $x$ and $y$.
Think of it as a verifier for ...
4
It is known that $\mathsf{UP= NP}$ implies $\mathsf{SpanP = \#P}$ since Kobler, Schoning, and Toran proved that $\mathsf{UP= NP}$ if and only if $\mathsf{SpanP = \#P}$. It is easy to see that $\mathsf {\#P}$ is contained in $\mathsf {SpanP}$.
A function $f : Σ^* →\mathbb N$ is in $\mathsf{SpanP}$ if there is an $\mathsf {NP}$ Turing machine transducer $M$ ...
answered Jan 19 '14 at 0:38
Mohammad Al-Turkistany
20.4k4 gold badges57 silver badges144 bronze badges
3
Question 1: For a function $f(n)$ lets say that $f$ is sub-polynomial if $\forall \epsilon > 0, f(n) = O(n^\epsilon)$. The Exponential Time Hypothesis (ETH) states that 3-SAT needs $2^{\epsilon n}$ time for some $\epsilon > 0$. Let's postulate a much weaker version, ``Weak Exponential Time Hypothesis'' (WETH): There exists an $\epsilon > 0$ such ...
Only top voted, non community-wiki answers of a minimum length are eligible