Skip to main content
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 = ...
Lance Fortnow's 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-...
Daniel Apon's user avatar
  • 6,011
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 ...
Joshua Grochow's user avatar
8 votes

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

It appears that nobody has provided an answer to this question. One reason may be that it's not clear what you mean by "the rest of the polynomial hierarchy". Indeed, it's not clear that P=...
Eric Allender's 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 ...
Emil Jeřábek's 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

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 ...
Kaveh's user avatar
  • 21.7k
5 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 ...
Eric Allender's user avatar
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 ...
Izaak Meckler's 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}$ ...
daniello's user avatar
  • 3,276
2 votes

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-...
Michael Wehar's 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 ...
usul's user avatar
  • 7,615
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 ...
Michael Wehar's user avatar

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