Structural Complexity Theory

learn more… | top users | synonyms

3
votes
0answers
74 views

Symmetry of optimal solutions to discrete optimization problems

Given a graph, say one wants to find the clique number, independence number, chromatic number, vertex cover number etc., one knows that a solution exists. However if the solution space has more than ...
7
votes
1answer
116 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 ...
33
votes
0answers
603 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
763 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 ...
15
votes
1answer
249 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? ...
9
votes
1answer
549 views

Does $\mathsf{EXP}=\mathsf{NEXP}$ imply $\mathsf{E}=\mathsf{NE}$?

Does $\mathsf{EXP}=\mathsf{NEXP}$ imply $\mathsf{E}=\mathsf{NE}$?
16
votes
3answers
667 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
1k 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.