# Tag Info

### What are the consequences of $\mathsf{L}^2 \subseteq \mathsf{P}$?

• 2,271
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
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 ...
• 35.8k
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 ...

### "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

### 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,973

### 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 ...
• 35.8k
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 ...
• 35.8k
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 ...
• 14.8k
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

### 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 ...
Accepted

• 250

### 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 ...
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

### 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 = ...
• 4,900