Structural Complexity Theory

learn more… | top users | synonyms

6
votes
1answer
235 views

Is every coNP-complete language P-isomorphic to an P-immune coNP-complete language? OR Is there a P-immune coNP-complete language?

A set is $\mathsf{P}$-immune iff it has no non-trivial $\mathsf{P}$ subset. Is every $\mathsf{coNP}$-complete language $\mathsf{P}$-isomorphic to an $\mathsf{P}$-immune $\mathsf{coNP}$-complete ...
14
votes
2answers
214 views

Poly time superset of NP complete language with infinitely many strings excluded from it

For any arbitrary NP complete language is there always a polytime superset the complement of which is also infinite? A trivial version which does not stipulate the superset to have infinite ...
8
votes
1answer
217 views

Does the isomorphism conjecture imply exponential lower bounds on witnesses density?

The Isomorphism Conjecture of Berman and Hartmanis states that all $NP$-complete sets are polynomial time isomorphic to each other. This means that $NP$-complete problems are efficiently reducible to ...
19
votes
0answers
358 views

What is the power of general poly-size permutation branching programs?

Call $\mathsf{PPBP}$ the class of languages decided by poly-size families of permutation branching programs, which are layered branching programs (i.e., the ones defined here) whose transitions ...
14
votes
1answer
308 views

$\mathsf{EXP}$ vs $\oplus\mathsf{EXP}$

In our recent work, we resolve a computational problem which arose in combinatorial context, under assumption that $\mathsf{EXP} \ne \mathsf{\oplus{}EXP}$, where $\mathsf{\oplus{}EXP}$ is the $\mathsf{...
4
votes
0answers
249 views

Any known connections between open problems for time and space: P vs L, NP vs NL, BPP vs BPL, ⊕P vs ⊕L

It would be nice to show that $P=L$ implies $NP=NL$. Or, $NP=NL$ implies $UP=UL$. Or maybe, $⊕P = ⊕L$ implies $PP = PL$. Are there any known connections between the problems: P vs L, UP vs UL, NP ...
3
votes
0answers
106 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 ...
9
votes
1answer
124 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 ...
39
votes
2answers
1k 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 = \mathsf{...
21
votes
1answer
798 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 ...
16
votes
1answer
297 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
635 views

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

Does $\mathsf{EXP}=\mathsf{NEXP}$ imply $\mathsf{E}=\mathsf{NE}$?
17
votes
3answers
692 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 ...
13
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.