Unanswered Questions
221 questions with no upvoted or accepted answers
31
votes
0
answers
879
views
The complexity of checking whether two DAG have the same number of topological sorts
This problem is highly related to the CNF one.
Here is the problem: given two DAG (directed acyclic graphs), if they have the same counting of topological sorts, answer "Yes", otherwise, answer "No".
...
- 2,397
29
votes
0
answers
1k
views
Does $EXP\neq ZPP$ imply sub-exponential simulation of BPP or NP?
By simulation I mean in the Impaglazzio-Widgerson [IW98] sense, i.e. sub-exponential deterministic simulation which appears correct i.o to every efficient adversary.
I think this is a proof: if $EXP\...
- 22.2k
22
votes
0
answers
831
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 ...
21
votes
0
answers
295
views
Descriptive complexity characterization of TimeSpace classes
Are there descriptive complexity characterizations for TimeSpace complexity classes like $\mathsf{SC^i}= \mathsf{DTimeSpace}(n^{O(1)},O(\lg^i n))$?
- 10.5k
20
votes
0
answers
526
views
Interesting PCP characterization of classes smaller than P?
The PCP theorem, $\mathsf{NP} = \mathsf{PCP}(\mathsf{log}\, n, 1)$, involves probabilistically checkable proofs with polynomial time verifiers, so the smallest class that can be characterized in this ...
- 2,331
17
votes
0
answers
430
views
Intermediate problems between PSPACE and EXPTIME
Intermediate problems between P and NP are quite famous, and are sometimes considered as complexity classes by themselves.
Do you know of any problem that is known to be PSPACE-hard and in EXPTIME, ...
- 9,624
17
votes
0
answers
538
views
What if an $\mathsf L$-complete problem has $\mathsf{NC}^1$ circuits? More generally, what evidence is there against $\mathsf{NC}^1=\mathsf{L}$?
Edit: let me reformulate the question in a more specific way (and change the title accordingly). A slightly edited version of the original question follows.
Is there a result comparable to the Karp-...
- 5,898
16
votes
0
answers
546
views
An algebra of complexity classes
A key feature of unrelativized computation is its composability out of smaller fragments, and to partially capture the composability, I came up with an algebra of fine-grained complexity classes.
For ...
- 2,842
15
votes
0
answers
505
views
Is there a P-complete language X such that succinct-X is in P?
I came across a paper called "A Note on Succinct Representation of Graphs". It seems that in the discussion section they claim that for any problem $X$ that is $\mathrm{P}$-hard under projections, $\...
- 119
15
votes
0
answers
555
views
Williams' Method, Natural Proofs and Constructivity
I have some questions on the previous question which is written bellow.
Natural Proof and Constructivity : The topic of the previous question
Recently, Ryan Williams proved that Constructivity in ...
CommunityBot
- 1
15
votes
0
answers
365
views
Intersecting Complexity Classes with Advice
In on hiding information from an oracle, the authors (Abadi, Feigenbaum, and Kilian) wrote:
$(\mathsf{NP/poly} \cap \mathsf{co\text-NP}{/poly})$ ... is not known to be equal to $(\mathsf{NP} ...
- 9,598
14
votes
0
answers
555
views
Does ${\bf L} \neq {\bf NL}$ imply ${\bf P} \neq {\bf NP}$?
This question is inspired by this question Implications between $\mathsf{L}=\mathsf{P}$ and $\mathsf{NL}=\mathsf{NP}$?
We do know that ${\bf L}$ could equal ${\bf NL}$ and at the same time ${\bf P}$ ...
CommunityBot
- 1
14
votes
0
answers
248
views
Do circuits allow to derive EXPSPACE hardness results?
It seems that encoding an NP-complete problem succinctly often makes it nexptime-complete. For instance, 3SAT or HAMILTONIAN PATH become NEXPTIME-complete when the encoding is succint, eg using ...
CommunityBot
- 1
13
votes
0
answers
752
views
Impact of proof of NP=co-NP on RP vs co-RP Question?
It is known that P ⊆ RP ⊆ NP and P ⊆ co-RP ⊆ co-NP. In an oracle world:
If NP=co-NP, does RP=co-RP=ZPP follow automatically or does it require additional conditions?
If NP=PSPACE, does RP=co-RP=ZPP ...
- 21.1k
12
votes
0
answers
375
views
NP complete problem help
I'm currently trying to find a reduction to this problem:
Given a set S of n points (in the plane) in general position, is there a set of at least k triangles (formed using only points in S as ...
- 220