28
votes
What are the consequences of $\mathsf{L}^2 \subseteq \mathsf{P}$?
$
\newcommand{\DSPACE}{\mathsf{DSPACE}}
\newcommand{\L}{\mathsf{L}}
\newcommand{\P}{\mathsf{P}}
\newcommand{\DTIME}{\mathsf{DTIME}}
$
$\L^2 \subseteq \P$ would refute the Exponential Time Hypothesis.
...
- 2,281
28
votes
Accepted
What are the consequences of $\mathsf{L}^2 \subseteq \mathsf{P}$?
The following is an obvious consequence:
$\mathsf{L}^{1+\epsilon} \subseteq \mathsf{P}$ would imply $\mathsf{L} \subsetneq \mathsf{P}$ and therefore $\mathsf{L} \neq \mathsf{P}$.
By the space ...
- 556
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 ...
- 36.2k
12
votes
Accepted
Does P/poly $\neq$ NP/poly have any interesting implications?
Emil Jeřábek' comment answers the question:
P/poly $=$ NP/poly is equivalent to NP $\subseteq$ P/poly
Note the corollary
P/poly $\neq$ NP/poly implies P $\neq$ NP.
Proof of corollary:
P/poly ...
11
votes
"Berman-Hartmanis Conjecture Separates NP From All Super-Poly. DTIME Classes" -- Worthy of arXiv.org?
I'm glad you are interested in complexity but there are some issues in your paper. Your techniques relativize and there is an oracle relative to which the Berman-Hartmanis conjecture is true and NP = ...
- 8,546
8
votes
Evidence that PPAD is hard?
(I guess no one ever answered this older question with the newer results; here you go:)
Assuming the existence of quasipolynomially-hard indistinguishability obfuscation and subexponentially-hard one-...
- 5,983
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 ...
- 36.2k
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 ...
- 36.2k
7
votes
Accepted
Does $NP=PP$ collapse the counting hierarchy?
We have
$$\mathrm{PP^{NP}\subseteq PP^{ModPH}\subseteq P^{PP}},$$
thus by the assumption,
$$\mathrm{PP^{PP}\subseteq PP^{NP}\subseteq P^{PP}\subseteq P^{NP}\subseteq NP}$$
as under the assumption, NP ...
- 15.3k
7
votes
Accepted
L/P/PSpace vs P/NP
The only known proper containment is still $L \subsetneq PSPACE$, though they are all widely believed to be different. All the rest are still wide-open.
The recent work on ``Fine-Grained Complexity",...
- 111
7
votes
ETH: k-SAT vs. SAT?
The difference between your definitions is that the clause width in $s_\omega$ is allowed to grow with the number of variables, while for $s_\infty$ it is arbitrarily large but constant.
It's a ...
- 349
7
votes
Accepted
Can one amplify P=NP beyond P=PH?
From Russell Impagliazzo's comment:
As a way of formalizing
what languages are in $\mathsf{P}$ if $\mathsf{P}=\mathsf{NP}$,
Regan introduced the complexity class $\mathsf{H}$.
A language $...
5
votes
Can one amplify P=NP beyond P=PH?
As I wrote in my answer to the other question
let's make the argument constructive and uniform in the number of alternations
by giving an algorithm that solves $\Sigma^P_k$ assuming that
we have a ...
- 21.3k
5
votes
Mathematical implications of complexity theory conjectures outside TCS
You can use complexity theoretic conjectures to prove things about, e.g., the representation theory of the symmetric group (see this blog post). Roughly speaking, since the word problem of the ...
- 431
5
votes
ETH: k-SAT vs. SAT?
A better way to define these exponents is if you ask about the running time in the form $c^n\cdot poly(|F|)$, where $poly(|F|)$ is an arbitrary polynomial of the input size. Then artifacts like the $3^...
- 250
4
votes
What are consequences of the collapse of CH?
You could also ask similar questions about the polynomial hierarchy. The consensus in the research community is that PH is unlikely to collapse ... but I can't think of any dramatic consequences that ...
3
votes
Accepted
Limits of variants of Independent Set?
Question 1: For a function $f(n)$ lets say that $f$ is sub-polynomial if $\forall \epsilon > 0, f(n) = O(n^\epsilon)$. The Exponential Time Hypothesis (ETH) states that 3-SAT needs $2^{\epsilon n}$ ...
- 3,236
2
votes
Evidence that PPAD is hard?
While this has been bumped anyway, maybe I can have the hubris to mention a heuristic that comes to mind.
An NP-complete problem is, given a circuit, is there an input that evaluates to True?
This ...
- 7,140
1
vote
What happens to complexity classes if all $\#P$ problems have polynomial-time algorithms?
By definition, $\mathbb{P} = \mathbb{NP}$, since any $\mathbb{NP}$ problem could be solved by answering the question "Is the # of accepting paths non-zero", which by assumption, can be calculated in $\...
- 3,741
1
vote
What are the consequences of $\mathsf{L}^2 \subseteq \mathsf{P}$?
Claim: If $L^k \subseteq P$ for some $k > 2$, then $P \neq \log(CFL)$ and $P \neq NL$.
Suppose that $L^k \subseteq P$ for some $k > 2$.
From "Memory bounds for recognition of context-...
- 5,005
1
vote
Problems that can be used to show polynomial-time hardness results
Intersection non-emptiness problem: Given two DFA's $D_1$ and $D_2$, is $L(D_1) \cap L(D_2) \neq \emptyset$?
This is classically known to be solvable in quadratic time by solving reachability in the ...
- 5,005
Only top scored, non community-wiki answers of a minimum length are eligible