Add X as a hypothesis, where X is not known to be either true or false.
8
votes
0answers
159 views
Is it known that $NEXP = \Sigma_2 \implies NEXP = MA$?
Is it known whether the implication $\mathsf{NEXP} = \Sigma_2 \implies \mathsf{NEXP} = \mathsf{MA}$ holds?
(The question is inspired by well-known $\mathsf{NEXP} \subseteq \mathsf{P/poly} ...
0
votes
0answers
76 views
Breaking secure pseudorandom generators by assuming BPP != P
Suppose we find some problem X that is in BPP but not in P. Also, suppose we have access to a random oracle R. Do X and R allow us to break any claimed secure pseudo-random number generator?
(Note ...
4
votes
1answer
203 views
On the proof of Meyer's Theorem
Meyer's theorem is one of the classical results about collapse of the polynomial hierarchy such as famous Karp Lipton's theorem, and states that $EXP \subseteq P/poly \Rightarrow EXP = \Sigma_{2}^{p} ...
1
vote
0answers
68 views
Conditional Results on Bounded Depth Circuit Hierarchy
$\mathsf{AC,ACC,TC}$-hierarchy are basic bounded depth circuit hierarchies.
$AC$-hierarchy is $\bigcup _{i =0}^{\infty} AC^{i} $ , where $AC^{i}$ is the $i$-th level of the hierarchy: a family of ...
4
votes
1answer
127 views
bounded language complete for NSPACE(log n)?
What are the consequences of a sparse language being complete for $\mathsf{NSPACE(\log n)}$ under deterministic $O(\log n)$-space many-one reductions? Is there an analog of Mahaney's Theorem for ...
11
votes
1answer
409 views
Consensus on P = NP in a world where RP = NP
$RP = NP$ is widely conjectured to be false.
But imagine for a moment that it is true. In such case, how likely would be that $P = NP$?
Put in other words: in a world where $RP = NP$, what might ...
17
votes
1answer
251 views
Consequences of $BQP \subseteq P/poly$?
While Adleman's theorem shows, that $\mathsf{BPP} \subseteq \mathsf{P}/\text{poly}$, I'm not aware of any literature investigating the possible inclusion of $\mathsf{BQP} \subseteq ...
1
vote
1answer
77 views
Consequences of a $p$-optimal proof system for $\operatorname{TAUT}$
I'm reading a paper which shows the result:
$(1)$ There is a $p$-optimal proof system for $\operatorname{TAUT}$. $\Leftrightarrow$
$(2)$ $L_{\leq}$ is a $P$-bounded logic for $P$.
Both $(1)$ and ...
27
votes
0answers
481 views
What are the consequences of $\mathsf{L}^2 \subseteq \mathsf{P}$?
We know that $\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{P}$ and that $\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{L}^2 \subseteq $ $\mathsf{polyL}$, where $\mathsf{L}^2 = ...
7
votes
1answer
477 views
Does $\mathsf{EXP}=\mathsf{NEXP}$ imply $\mathsf{E}=\mathsf{NE}$?
Does $\mathsf{EXP}=\mathsf{NEXP}$ imply $\mathsf{E}=\mathsf{NE}$?
8
votes
0answers
218 views
VNP = VP versus complexity classes in Arithmetic Geometry
What is the implication of $VNP = VP$ to cryptography schemes such as Elliptic curve/Abelian Variety/Arithmetic Geometry based cryptography? Are there any papers or books that talk about sophisticated ...
23
votes
2answers
649 views
Consequences of $SAT \in BQP$
As a TCS amateur, I'm reading some popular, very introductory material on quantum computing. Here are the few elementary bits of information I've learned so far:
Quantum computers are not known to ...
29
votes
0answers
831 views
Can one amplify P=NP beyond P=PH?
In Descriptive Complexity, Immerman has
Corollary 7.23. The following conditions are equivalent:
1. P = NP.
2. Over finite, ordered structures, FO(LFP) = SO.
This can be thought of as ...
21
votes
3answers
1k views
Consequences of Factoring being in P?
Factoring is not known to be NP-complete. This question asked for consequences of Factoring being NP-complete. Curiously, no one asked for consequences of Factoring being in P (maybe because such a ...
19
votes
1answer
413 views
Problems in NP but not in Average-P/poly
The Karp–Lipton Theoem states that if $\mathsf{NP} \subset \mathsf{P/poly}$, then $\mathsf{PH}$ collapses to $\mathsf{\Sigma^P_2}$. Therefore, assuming separations between $\mathsf{\Sigma^P_2}$ and ...
11
votes
0answers
467 views
Consequences of UP equals NP
EDIT at 2011/02/08:
After some references finding and reading, I decided to separate the original question into two separate ones. Here's the part concerning UP vs NP, for the syntactic and semantic ...
17
votes
4answers
591 views
If P = BQP, does this imply that PSPACE (= IP) = AM?
Recently, Watrous et al proved that QIP(3) = PSPACE a remarkable result. This was a surprising result to myself to say the least and it set me off thinking...
I wondered what if Quantum Computers ...
26
votes
4answers
664 views
Hardness of approximation assuming NP != coNP
Two of the common assumptions for proving hardness of approximation results are $P \neq NP$ and Unique Games Conjecture. Are there any hardness of approximation results assuming $NP \neq coNP$ ? I am ...
25
votes
3answers
866 views
Consequences of existence of a strongly polynomial algorithm for linear programming?
One of the holy grails of algorithm design is finding a strongly polynomial algorithm for linear programming, i.e., an algorithm whose runtime is bounded by a polynomial in the number of variables and ...
26
votes
3answers
1k views
A decision problem which is not known to be in PH but will be in P if P=NP
Edit: As Ravi Boppana correctly pointed out in his answer and Scott Aaronson also added another example in his answer, the answer to this question turned out to be “yes” in a way which I had not ...
15
votes
2answers
540 views
NC = P consequences?
The Complexity Zoo points out in the entry on EXP that if L = P then PSPACE = EXP. Since NPSPACE = PSPACE by Savitch, as far as I can tell the underlying padding argument extends to show that ...
45
votes
4answers
1k views
Problems that can be used to show polynomial-time hardness results
When designing an algorithm for a new problem, if I can't find a polynomial time algorithm after a while, I might try to prove it is NP-hard instead. If I succeed, I've explained why I couldn't find ...
23
votes
2answers
1k views
Status of Impagliazzo's Worlds?
In 1995, Russell Impagliazzo proposed five complexity worlds:
1- Algorithmica: $P=NP$ with all the amazing consequences.
2- Heuristica: $NP$-complete problems are hard in the worst-case ($P \ne NP$) ...
22
votes
3answers
1k views
Does $VP \neq VNP$ imply $P \neq NP$?
As far as I understand, the geometric complexity theory program attempts to separate $VP \neq VNP$ by proving that the permament of a complex-valued matrix is much harder to compute than the ...
10
votes
0answers
285 views
Collapsing of exptime and alternation bounded turing machine
This question was already asked on math overflow, but I did not find any answer to my question (or let say the answer was that up to the knowledge of those people, no answer were known)
Let C be a ...
25
votes
0answers
541 views
Does $EXP\neq ZPP$ imply sub-exponential simulation of BPP or NP?
By simulation I mean in the Impaglazzio-Widgerson [IW98] sense, i.e. sub-exponential deterministic simulation which appears correct i.o to every efficient adversary.
I think this is a proof: if ...
22
votes
2answers
743 views
Evidence that PPAD is hard?
There is often-quoted philosophical justification for believing that P != NP even without proof. Other complexity classes have evidence that they are distinct, because if not, there would be ...
23
votes
2answers
670 views
What are the consequences of Parity-L = P?
Parity-L is the set of languages recognized by a non-deterministic Turing machine which can only distinguish between an even number or odd number of "acceptance" paths (rather than a zero or non-zero ...
21
votes
4answers
797 views
What specific evidence is there for P = RP?
RP is the class of problems decidable by a nondeterministic Turing machine that terminates in polynomial time, but that is also allowed one-sided error. P is the usual class of problems decidable by ...
