Skip to main content

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
65 votes
5 answers
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 ...
Robin Kothari's user avatar
55 votes
2 answers
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 "...
András Salamon's user avatar
49 votes
4 answers
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{...
argentpepper's user avatar
  • 2,281
40 votes
3 answers
4k 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 ...
Benno's user avatar
  • 403
38 votes
3 answers
5k 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 ...
Giorgio Camerani's user avatar
37 votes
2 answers
6k 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$) ...
Mohammad Al-Turkistany's user avatar
36 votes
3 answers
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 $$(\...
András Salamon's user avatar
36 votes
2 answers
2k 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 ...
Giorgio Camerani's user avatar
34 votes
5 answers
3k 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 "...
Aaron Roth's user avatar
  • 9,900
33 votes
3 answers
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 ...
Ian's user avatar
  • 2,747
32 votes
4 answers
889 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 ...
Shiva Kintali's user avatar
31 votes
4 answers
5k 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 ...
Denis's user avatar
  • 8,903
30 votes
3 answers
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 ...
Tsuyoshi Ito's user avatar
  • 16.5k
29 votes
2 answers
2k 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 ...
Niel de Beaudrap's user avatar
29 votes
0 answers
1k 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 $EXP\...
Sebastian Ben Daniel's user avatar
28 votes
1 answer
2k views

Consequences of Complete problems for NP intersects coNP

What are the consequences of having complete problems in $NP\cap coNP$?
Marcos Villagra's user avatar
28 votes
2 answers
2k views

Reasons to believe $P \ne NP \cap coNP$ (or not)

It seems that many people believe that $P \ne NP \cap coNP$, in part because they believe that factoring is not polytime solvable. (Shiva Kintali has listed a few other candidate problems here). On ...
Austin Buchanan's user avatar
27 votes
4 answers
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 ...
András Salamon's user avatar
27 votes
1 answer
939 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 ...
neophyte's user avatar
  • 531
25 votes
5 answers
3k views

Mathematical implications of complexity theory conjectures outside TCS

Do you know interesting consequences of (standard) conjectures in complexity theory in other fields of mathematics (i.e. outside of theoretical computer science)? I would prefer answers where: the ...
Sasho Nikolov's user avatar
22 votes
1 answer
1k 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{...
Martin Schwarz's user avatar
20 votes
1 answer
736 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 $\...
Sadeq Dousti's user avatar
  • 16.5k
20 votes
1 answer
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 ...
Hsien-Chih Chang 張顯之's user avatar
18 votes
4 answers
985 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 ...
Zelah 02's user avatar
  • 1,578
18 votes
4 answers
5k views

Consequences of $NP=coNP$ and $P\ne NP$?

We know that if $P=NP$ then the whole PH collapses. What if the polynomial hierarchy collapses partially ? (Or how to understand that PH could collapse above a certain point and not below ?) In ...
Xavier Labouze's user avatar
18 votes
1 answer
740 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 ...
Sasho Nikolov's user avatar
17 votes
4 answers
4k views

What would be the consequences of PH=PSPACE?

A recent question (see Consequences of NP=PSPACE) asked for the "nasty" consequences of $NP=PSPACE$. The answers list quite a few collapse consequences, including $NP=coNP$ and others, providing ...
Andras Farago's user avatar
16 votes
0 answers
541 views

Quantum Hardness of Finding Nash Equilibria

This question is inspired by the recent, beautiful work On the Cryptographic Hardness of Finding a Nash Equilibrium by Bitansky, Paneth, and Rosen. Their main result is that the existence of ...
Daniel Apon's user avatar
  • 6,011
15 votes
1 answer
492 views

$\mathsf{EXP}$ vs $\oplus\mathsf{EXP}$

In our recent work, we resolve a computational problem which arose in combinatorial context, under assumption that $\mathsf{EXP} \ne \mathsf{\oplus{}EXP}$, where $\mathsf{\oplus{}EXP}$ is the $\mathsf{...
Igor Pak's user avatar
  • 812
14 votes
1 answer
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$...
Thomas Klimpel's user avatar
13 votes
0 answers
396 views

Consequences of bipartite perfect matching not in NL?

Are any significant consequences known of $\text{BPM} \not\in \textsf{NL}$? I'm interested in the status of the following well-studied decision problem, in particular whether it is known to be in $\...
András Salamon's user avatar
12 votes
1 answer
1k 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 ...
Giorgio Camerani's user avatar
12 votes
1 answer
990 views

L/P/PSpace vs P/NP

in 1979 Hopcroft/ Ullman wrote that L ⊆ P ⊆ NP ⊆ PSpace is known but L ⊊ PSpace is the only proper (& trivial) containment known although all are conjectured to be proper containments, and "where ...
vzn's user avatar
  • 11k
12 votes
0 answers
408 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} \...
sdcvvc's user avatar
  • 1,291
11 votes
1 answer
1k views

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

Does $\mathsf{EXP}=\mathsf{NEXP}$ imply $\mathsf{E}=\mathsf{NE}$?
argentpepper's user avatar
  • 2,281
11 votes
2 answers
383 views

Consequence of PIT over $\Bbb Z[x_1,\dots,x_n]$ not having efficient algorithm

Given $p(x_1,\dots,x_n),q(x_1,\dots,x_n)\in \Bbb Z[x_1,\dots,x_n]$ such that coefficients of $p,q$ are bounded by $B$, does $p\equiv q$ hold? Schwartz-Zippel lemma applies here since it holds for ...
user avatar
10 votes
2 answers
519 views

ETH: k-SAT vs. SAT?

Let SAT$_v$ be the language of those instances of SAT that contain variables $[v] = \{0,1,\dots,v-1\}$, let $k$-SAT be the language of those instances of SAT in which every clause has at most $k$ ...
András Salamon's user avatar
10 votes
1 answer
319 views

Does $NC=P$ imply the collapse of Polynomial Hierarchy?

If $NC=P$ (with a constructive polynomial time algorithm that converts any $P$ time circuit to a $NC$ circuit), what impact would it have on the rest of the Polynomial Hierarchy? Couldn't find much in ...
J.Doe's user avatar
  • 478
10 votes
0 answers
230 views

Does a polynomial-time algorithm for factoring product of two primes imply a polynomial-time algorithm for factoring in general?

Is it known if the existence of a polynomial-time algorithm for the promise problem of factoring of numbers with two prime factors implies that factoring in general has a polynomial-time algorithm?
eof's user avatar
  • 101
10 votes
0 answers
174 views

Hardness in P: methods to show optimality of $O(m^2n)$-like time?

In recent years, there has been exciting work in proving lower bounds for polynomial-time problems conditional on conjectures like SETH or "All-Pairs-Shortest-Paths (APSP) cannot be solved in $O(|V|^{...
Dominik Peters's user avatar
10 votes
0 answers
363 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 ...
Arthur MILCHIOR's user avatar
9 votes
1 answer
366 views

Does $NP=PP$ collapse the counting hierarchy?

Suppose $NP=PP$. Then a simple argument shows that $PH^{PP}=NP$. Can we go one step further and get $PP^{PP}=NP$? The simple argument is Theorem If $NP=PP$ then $PH^{PP}=NP$. Proof $PP$ is closed ...
Lieuwe Vinkhuijzen's user avatar
9 votes
0 answers
535 views

Why do we believe $\mathsf{fewP \ne NP}$?

$\mathsf{fewP}$ ($\mathsf{NP}$ with few witnesses, see the zoo) is one of the important ambiguity-bounded sub-classes of $\mathsf{NP}$. There are interesting natural problems in this class that are ...
Mohammad Al-Turkistany's user avatar
9 votes
0 answers
564 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 ...
v s's user avatar
  • 2,208
7 votes
1 answer
366 views

"Berman-Hartmanis Conjecture Separates NP From All Super-Poly. DTIME Classes" -- Worthy of arXiv.org?

Do you believe this paper is worthy of arXiv.org? I have searched via Google, and to my knowledge, no one else has this result. I'm not asking you to fully scrutinize the paper, I'm just asking if you ...
Jake Thomas's user avatar
7 votes
0 answers
1k views

Does L=P imply any new complexity class separations?

If L=P then P is not equal to PSPACE. This follows from PSPACE properly containing L. I am wondering if L=P implies any stronger separation between complexity classes? Does it imply P is properly ...
Anonymous's user avatar
  • 4,041
4 votes
1 answer
211 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 $(...
Joachim's user avatar
  • 513
4 votes
1 answer
224 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? ...
András Salamon's user avatar
4 votes
1 answer
201 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 $\...
user13417's user avatar
4 votes
1 answer
1k 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} $...
echuly's user avatar
  • 549