Questions tagged [conditional-results]
Add X as a hypothesis, where X is not known to be either true or false.
55
questions
7
votes
1
answer
359
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 ...
- 71
3
votes
0
answers
66
views
Pseudodeterministically choosing elements from efficiently samplable distributions (or, the plausibility of a weak choice principle)
Suppose we have a poly-time samplable family of distribution. I.e., a family of distributions $D_n \subseteq \{0, 1\}^{\mathsf{poly}(n)}$ and an algorithm $S$ for which $D_n = (r \leftarrow^\$ \{0,1\}^...
- 431
2
votes
0
answers
56
views
Is there a complete and finite axiom scheme for conditional independence? (Graphoids)
Note: This is a better-written version of an unanswered question asked before on MathOverflow.
Question: Is there a complete and finite axiom scheme for conditional probability?
If so, is there a ...
- 503
9
votes
1
answer
345
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 ...
- 1,879
4
votes
1
answer
209
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?
...
- 18.9k
13
votes
0
answers
376
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 $\...
- 18.9k
10
votes
0
answers
229
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?
- 101
10
votes
0
answers
172
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|^{...
- 381
16
votes
0
answers
532
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 ...
- 5,963
11
votes
2
answers
376
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 ...
user34945
-2
votes
1
answer
334
views
What is the status of intermediate problems if P is not NP in worst way imaginable?
Assume $P\neq BPP\neq NP$ with caveat that there is a deterministic algorithm for every $NP$ complete problem with input size $n$ bits in $2^{(\log n)^{1+f(n)}}$ arithmetic operations on $\log n$ ...
- 12.6k
12
votes
1
answer
929
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 ...
- 10.9k
3
votes
1
answer
357
views
What happens to complexity classes if all $\#P$ problems have polynomial-time algorithms?
As title says what happens to other complexity classes if all $\#P$ (Sharp-P) problems have polynomial-time algorithms? What happens to PSPACE?
- 39
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$...
- 3,013
15
votes
1
answer
473
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{...
- 720
9
votes
2
answers
488
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$ ...
- 18.9k
26
votes
1
answer
912
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 ...
- 521
16
votes
4
answers
3k
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 ...
- 11.1k
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 ...
- 8,473
7
votes
0
answers
492
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 ...
- 20.8k
18
votes
1
answer
712
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 ...
- 18.1k
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 ...
- 18.1k
27
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 ...
- 1,156
3
votes
1
answer
188
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'...
- 31
12
votes
0
answers
395
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} \...
- 1,261
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} $...
- 549
2
votes
0
answers
110
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 $\...
- 549
4
votes
1
answer
199
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 $\...
- 41
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 ...
- 6,715
21
votes
1
answer
945
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{...
- 5,436
4
votes
1
answer
202
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 $(...
- 513
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{...
- 2,281
6
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 ...
- 4,001
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}$?
- 2,281
15
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 ...
- 1,079
9
votes
0
answers
559
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 ...
- 2,208
35
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 ...
- 6,715
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 "...
- 18.9k
37
votes
3
answers
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 ...
- 6,715
20
votes
1
answer
713
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 $\...
- 16.3k
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 ...
- 7,628
18
votes
4
answers
954
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 ...
- 1,578
32
votes
4
answers
873
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 ...
- 10.6k
31
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 ...
- 2,707
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 ...
- 16.4k
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 $$(\...
- 18.9k
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 ...
- 13.4k
36
votes
2
answers
5k
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$) ...
- 20.8k
38
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 ...
- 383
10
votes
0
answers
359
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 ...
- 1,521