Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [structural-complexity]

Structural Complexity Theory

3
votes
1answer
132 views

Are there any parameterized problems in non-uniform FPT that are suspected (but not proven) to be in uniform-FPT?

Getting Started Consider a parameterized problem $F$. We use $n$ to denote the input size and $k$ to denote the parameter. Consider the fixed levels of $F$ which we denote by $\{F_k\}_{k\in\mathbb{...
18
votes
1answer
406 views

What is the minimum complexity oracle that separates PSPACE from the polynomial hierarchy?

Background It is known that there exists an oracle $A$ such that, $PSPACE^A \neq PH^A$. It is even known that the separation holds relative to a random oracle. Informally, one may interpret ...
12
votes
1answer
169 views

Reductions between languages of different densities?

The density of a language $X$ is a function $d_X \colon \mathbb{N} \to \mathbb{N}$ defined as $$d_X(n) = |\{x\in X \mid |x| \le n\}|.$$ Suppose $A$ and $B$ are languages over some finite alphabet, $A$ ...
9
votes
0answers
191 views

Is the infinitely-often version of Ladner's theorem known?

We say two languages $\;\;\; L\hspace{.02 in},\hspace{-0.02 in}L' \: \subseteq \: \{\hspace{-0.02 in}0,\hspace{-0.05 in}1\hspace{-0.03 in}\}^* \;\;\;$ agree infinitely-often with each other if and ...
7
votes
1answer
270 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
343 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
240 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 ...
20
votes
0answers
480 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 ...
13
votes
1answer
368 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{...
5
votes
0answers
633 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 ...
4
votes
0answers
130 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
184 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 ...
45
votes
4answers
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
849 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
351 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
710 views

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

Does $\mathsf{EXP}=\mathsf{NEXP}$ imply $\mathsf{E}=\mathsf{NE}$?
17
votes
3answers
789 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 A ...
14
votes
1answer
2k 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.