Questions tagged [structural-complexity]
Structural Complexity Theory
21 questions
6
votes
1
answer
173
views
How to intuitively express the hardness of Minicrypt and Cryptomania?
My question is as stated in the title. To give an example of “intuitively express”, it’s like: we often say
Algorithmica means “NP is easy”,
Heuristica means “NP is hard on worst-case but easy on ...
- 191
1
vote
0
answers
101
views
Is complexity class containment preserved relative to any oracle?
That is, suppose $A\subseteq B$ for two complexity classes $A$ and $B$. Is it the case that for any oracle $C$, and any definitions $A^*$ and $B^*$ of $A$ and $B$, we have ${A^*}^C\subseteq {B^*}^C$? (...
5
votes
2
answers
446
views
Are there problems in $DTIME(n^k) - DTIME(n^{k-1})$ that are not hard for $DTIME(n^{k-1})$ under nearly linear time reductions?
Background
It can be challenging to find computational problems that are solvable in $DTIME(n^k) - DTIME(n^{k-1})$ where $k \geq 2$.
Although some natural problems are known to exist, many of them ...
- 5,167
3
votes
1
answer
298
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{...
- 5,167
18
votes
1
answer
887
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 ...
- 5,167
12
votes
1
answer
216
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$ ...
- 19.2k
9
votes
0
answers
270
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 ...
user6973
7
votes
1
answer
304
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 ...
- 405
15
votes
2
answers
432
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 ...
- 405
8
votes
1
answer
273
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 ...
- 21.1k
22
votes
0
answers
800
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 ...
- 5,628
15
votes
1
answer
497
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{...
- 812
5
votes
0
answers
1k
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 ...
- 5,167
4
votes
0
answers
147
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 ...
- 13.3k
10
votes
1
answer
217
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 ...
- 2,291
49
votes
4
answers
2k
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{...
- 2,291
22
votes
1
answer
966
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 ...
- 2,013
17
votes
1
answer
480
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? (...
- 1,311
11
votes
1
answer
1k
views
Does $\mathsf{EXP}=\mathsf{NEXP}$ imply $\mathsf{E}=\mathsf{NE}$?
Does $\mathsf{EXP}=\mathsf{NEXP}$ imply $\mathsf{E}=\mathsf{NE}$?
- 2,291
17
votes
3
answers
928
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 captures its essence.
Problem: Let A be a deterministic algorithm for 3-SAT. Is the
problem of completely simulating the ...
- 5,793
14
votes
1
answer
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.