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. ...
user avatar
  • 2,271
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 ...
user avatar
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 ...
user avatar
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 = ...
user avatar
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-...
user avatar
  • 5,973
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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",...
user avatar
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 ...
user avatar
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

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 ...
user avatar
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 ...
user avatar
  • 21.3k
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^...
user avatar
  • 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 ...
user avatar
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}$ ...
user avatar
  • 3,236
2 votes

NC = P consequences?

Here's a little more detail from the perspective of simulating time-space bounded Alternating Turing machine. Suppose that $P = NC$. Since $NC = ATISP((\log(n))^{O(1)}, O(\log(n)))$, we get $$P = ...
user avatar
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 ...
user avatar
  • 7,090
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 $\...
user avatar
  • 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-...
user avatar
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 ...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible