Structural Complexity Theory
7
votes
1answer
94 views
Can $\log^k n$ alternations be simulated in $\mathsf{NC}^k$?
Let $\mathsf{ATISP}(f(n), g(n))$ be the class of languages decided by alternating Turing machines that halt in time $f(n)$ using space $g(n)$. Let $\mathsf{AALTSP}(f(n), g(n))$ be the class of ...
27
votes
0answers
478 views
What are the consequences of $\mathsf{L}^2 \subseteq \mathsf{P}$?
We know that $\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{P}$ and that $\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{L}^2 \subseteq $ $\mathsf{polyL}$, where $\mathsf{L}^2 = ...
21
votes
1answer
671 views
Algorithms and structural complexity theory
Many important results in computational complexity theory, and in particular "structural" complexity theory, have the interesting property that they can be understood as fundamentally following (as I ...
11
votes
0answers
168 views
Strongly Regular Graph and GI-Completeness
It is not known if graph isomorphism (GI) for strongly regular graphs (SRGs) is in P. Are there any hints that it might or might not be GI-Complete? Are there any strong consequences in such cases? ...
7
votes
1answer
476 views
Does $\mathsf{EXP}=\mathsf{NEXP}$ imply $\mathsf{E}=\mathsf{NE}$?
Does $\mathsf{EXP}=\mathsf{NEXP}$ imply $\mathsf{E}=\mathsf{NE}$?
15
votes
3answers
619 views
How Hard is Exact Simulation of Algorithms, and a Related Operation on Complexity Classes
Teaser
Since the problem is longish here is a special case that capture its essense.
Problem: Let A be a detrministic algorithm for 3-SAT. Is the
problem of completely simulating the algorithm ...
12
votes
1answer
942 views
What are the classic papers from the recursion theoretic area of complexity theory?
Two papers I would include are:
D. Kozen, "Indexing of subrecursive classes", STOC, 1978.
R. Ladner, "On the Structure of Polynomial Time Reducibility", JACM, 1975.
