# Tag Info

## Hot answers tagged structural-complexity

27

$\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. If $\L^2 \subseteq \P$ then by a padding argument $\DSPACE(n) \subseteq \DTIME(2^{O(\sqrt n)})$. This means that the satisfiability problem $\mathsf{SAT} \... 27 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 hierarchy theorem,$\forall \epsilon > 0: \mathsf{L} \subsetneq \mathsf{L}^{1+\epsilon}$. If$\mathsf{L}^{1+\epsilon} \subseteq \mathsf{P}$then$\mathsf{L} \...

14

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 polynomially sparse set in $\oplus \mathsf{P} \backslash \mathsf{P}$. Given how far apart we think $\mathsf{P}$ and $\oplus \mathsf{P}$ are - e.g. Toda showed ...

13

I don't see how that would immediately follow: the isomorphism conjecture is about languages, and doesn't seem to have any implications about the witness structure of NP verifiers. (Every language has infinitely many different verifiers for it, and you could potentially rig those verifiers to do odd things.) But your question reveals another very natural ...

11

I believe all known GI-completeness results are functorial (definition in the paper), and Babai has recently shown (ITCS 2014, free author's copy) - based on bounds on the structure of automorphism groups of strongly regular graphs - that there is no functorial reduction from GI to strongly regular GI.

10

Every $\mathsf{coNP}$-complete set contains an infinite subset in $\mathsf{P}$ assuming that pseudorandom generators exist, and secure one-way permutations exist. In other words, assuming that these two conjectures are true, no $\mathsf{coNP}$-complete set is P-immune. As pointed out in the comments by Lance, this is implied by Theorem 4.4 of Glasser,...

9

I believe if you trace through the argument given, e.g., in Section 4.1 of Ker-I Ko's survey, you get an upper bound of $\mathsf{DTIME}(2^{2^{O(n^2)}})$. In fact, we can replace $n^2$ here with any function $nf(n)$ where $f(n) \to \infty$ as $n \to \infty$. This isn't quite what was asked for, but it's close. In particular, using the translation between ...

8

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 current upper bound is $n^{O(\log n)}$-time, and because it reduces to graph isomorphism, stands as a significant obstacle to putting graph iso into P. Makes ...

8

Let $A$ be any language not in $L$, such that $A$ has density $2^{o(n)}$, and define $$B = \{s \circ 1 | s \in \{0,1\}^*\} \cup \{s \circ 0 | s \in A\}.$$ Here $\circ$ is concatenation. The language $B$ has density $\Omega(2^n)$, which is superpolynomial in $2^{o(n)}$. On the other hand, $A$ and $B$ log-space reduce to each other ($A$ to $B$ by ...

6

In Downey and Fellows' 2013 book (Fundamentals of Parameterized Complexity; Section 2.2), they mention an example of a problem in non-uniform FPT (Graph Linking Number) and briefly discuss that it's open whether this problem is in uniform FPT. This problem seems fairly natural. When considering non-uniform parameterized complexity, one can look at many ...

5

Interesting question. The statement for every NP-complete $L$, there is $U$ in P such that $L \subseteq U$ and $U^c$ is infinite. is equivalent to: for every NP-complete $L$, complement of $L$ contains an infinite P set. which is in turn equivalent to every coNP-complete set contains an infinite P set. which is by symmetry the same as ...

4

Josh's answer uses two conjectures and both of them are considered to be highly likely to be correct by experts even if not proven yet. A positive answer means that at least one of the two conjecture is incorrect. That would be a major very surprising result. In other words, it is highly unlikely that the answer to your question is positive, and even if ...

1

You might have the right idea. Let $X'$ be a tally language (only composed of strings of 1-s) in $DTIME(n^k) -DTIME(n^{k-1})$. It is routine to construct such a set using the classical idea from the time hierarchy theorem. Alternatively one can use the construction you gave to construct $X'$. $X'$ is $DTIME(n^{k-1})$ hard by assumption. $X' \in DTIME(n)_{/O(... 1 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-free and context-sensitive languages", we know that$CFL \subseteq DSPACE(\log^2(n))$. By the space hierarchy theorem, we know that$DSPACE(\log^2(n)) \subsetneq ...

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