Questions tagged [conditional-results]

Add X as a hypothesis, where X is not known to be either true or false.

Filter by
Sorted by
Tagged with
34
votes
2answers
4k 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$) ...
64
votes
5answers
2k 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 ...
54
votes
2answers
4k 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 "...
37
votes
3answers
3k 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 ...
20
votes
1answer
1k 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 ...
29
votes
3answers
2k 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 ...
36
votes
3answers
4k 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 ...
29
votes
2answers
1k 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 ...
48
votes
4answers
2k 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 = \mathsf{...
31
votes
4answers
4k views

Consequences of NP=PSPACE

What would be the nasty consequences of NP=PSPACE? I am surprised I did not found anything on this, given that these classes are among the most famous ones. In particular, would it have any ...
26
votes
4answers
2k 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 ...
20
votes
1answer
676 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 $\...
17
votes
1answer
670 views

What evidence do we have for $\mathsf{UP} \neq \mathsf{NP}$?

Following Josh Grochow's suggestion, I am converting my comment from a previous question into a new question. What evidence do we have for $\mathsf{UP} \neq \mathsf{NP}$? Here $\mathsf{UP}$ is the ...
36
votes
3answers
2k 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 $$(\...
32
votes
4answers
860 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 ...
20
votes
1answer
770 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 \mathsf{P}/\text{...
31
votes
3answers
2k 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 ...
10
votes
0answers
350 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
746 views

What are consequences of the collapse of CH?

I don't grasp the full complexity of the counting hierarchy $CH$. I understand $CH$ is in $PSPACE$, and contains $PH$ within its second level, due to the Toda's theorem. But, what would be important ...
14
votes
1answer
1k views

Does P/poly $\neq$ NP/poly have any interesting implications?

$P/poly = NP/poly$ implies $NP \subseteq P/poly$, which in turn has interesting consequences like the collapse of the polynomial hierarchy. Are there interesting implications for $P/poly \neq NP/poly$...
10
votes
1answer
1k views

Does $\mathsf{EXP}=\mathsf{NEXP}$ imply $\mathsf{E}=\mathsf{NE}$?

Does $\mathsf{EXP}=\mathsf{NEXP}$ imply $\mathsf{E}=\mathsf{NE}$?
4
votes
1answer
176 views

Limits of variants of Independent Set?

Independent Set (IS) is the $\mathsf{NP}$-complete decision problem Input: graph $G$ with $v=|V(G)|$, integer $k$ Question: is there an independent set $S \subseteq V(G)$ with at least $k$ vertices? ...
2
votes
1answer
161 views

Intermediate Problems between FP and #P

Do there exist intermediate problems (in the sense of Ladner's Theorem) for FP vs. #P? I assume that something is known, because I read some papers concerned with FP/#P dichotomies. However, I couldn'...
4
votes
1answer
193 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 $\...