Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with conditional-results
Search options answers only
not deleted
user 129
Add X as a hypothesis, where X is not known to be either true or false.
3
votes
bounded language complete for NSPACE(log n)?
$\mathsf{L}=\mathsf{NL}$. Yes, there is an analog of Mahaney's Theorem for log-space. If there is a sparse set that is hard for $\mathsf{NL}$ under logspace reductions, then $\mathsf{L}=\mathsf{NL}$:
…
- 38.5k
8
votes
Accepted
Consequence of PIT over $\Bbb Z[x_1,\dots,x_n]$ not having efficient algorithm
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 …
- 38.5k
22
votes
Consequences of NP=PSPACE
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 fo …
- 38.5k
27
votes
What would be the consequences of $\mathsf{PH=PSPACE}$?
$\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 (b …
- 38.5k
8
votes
What specific evidence is there for P = RP?
It's important to note that saying "probabilistic reductions can [probably] be derandomized" is much stronger than P=RP. In fact, one formalization of the notion of derandomizing all randomized reduc …
- 38.5k
14
votes
Accepted
$\mathsf{EXP}$ vs $\oplus\mathsf{EXP}$
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 …
- 38.5k
8
votes
What are the consequences of $\mathsf{L}^2 \subseteq \mathsf{P}$?
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 …
- 38.5k
20
votes
Consequences of $NP=coNP$ and $P\ne NP$?
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 …
- 38.5k
20
votes
A decision problem which is not known to be in PH but will be in P if P=NP
Answering Scott Aaronson's question, but a bit too long for a comment, here is a construction of a language $L$ such that $P = NP$ implies $L \in P$, but $P \neq NP$ implies $L \notin PH$.
Let $M_1, …
- 38.5k
11
votes
If P = BQP, does this imply that PSPACE (= IP) = AM?
The answers of John Watrous and Andy Drucker are excellent for understanding some of the issues involved.
I'll just add to Andy's answer that, not only is no such implication known, but showing such …
- 38.5k