Unanswered Questions
710 questions with no upvoted or accepted answers
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\...
- 21.8k
24
votes
0
answers
523
views
Can we do integer addition in linear time?
Why, yes, of course. But I'm actually interested in the cost of computing the sum of multiple integers:
Input: A sequence of nonnegative integers $\langle X_i:i<k\rangle$ written in binary.
Output: ...
- 18.6k
19
votes
1
answer
2k
views
Complexity of interval cover problem
Consider the following problem $Q$: We are given an integer $n$, and $k$ intervals $[l_i,r_i]$ with $1\leq l_i\leq r_i\leq 2n$. We are also given $2n$ integers $d_1,…,d_{2n}\geq 0$. The task is to ...
CommunityBot
- 1
19
votes
1
answer
317
views
Is there a geometrical picture for adiabatic quantum computation?
In adiabatic quantum computation (AQC), one encodes the solution to an optimization problem in the ground state of a [problem] Hamiltonian $H_p$. To get to this ground state, you start in an easily ...
- 11.1k
18
votes
0
answers
550
views
Complexity of the densest $k$-subgraph problem on planar graphs
In the densest $k$-subgraph problem, one is given an undirected graph $G$ and wants to find a set of vertices $N$ with $|N| = k$ such that the number of edges in the subgraph of $G$ induced by $N$ is ...
- 99
17
votes
0
answers
984
views
Deeper look at Algorithmica?
Russell Impagliazzo published "A Personal View of Average-Case Complexity" (preprint) back in 1995.
He presented five possible worlds we could be living in, depending on how P and NP were related.
The ...
CommunityBot
- 1
17
votes
0
answers
438
views
Is Node Multiway Cut NP-complete on planar graphs when all terminals lie on the outer face?
I am interested in the following problem.
Node Multiway Cut on Planar Graphs with terminals on the outer face
Instance: A plane graph G, and integer k, and a set $S \subseteq V(G)$ of terminals which ...
- 359
16
votes
0
answers
506
views
a geometric variant of k-medians. NP-hard or in P?
The following problem is a special case of k-medians. Is it NP-hard? Is it in P?
Input: $n$ points $(x_1,y_1), (x_2,y_2), \ldots, (x_n, y_n)$ with each $y_i \ge 0$, and an integer $k$.
Output: a set ...
- 10.9k
16
votes
0
answers
495
views
Is graph coloring complete for poly-APX?
Is the graph coloring problem complete for poly-APX under C-reductions
(alternatively, under AP-reductions)? For the graph coloring problem, speaking of a feasible solution means a proper coloring for ...
- 6,795
16
votes
0
answers
1k
views
Phase Transitions in NP Hard Problems
SAT Problems have a phase transition that depends on the ratio $r$ of variables to clauses. Below $r$, SAT problems are solvable quickly; above, they become difficult. The same is true of NP ...
- 2,648
15
votes
0
answers
515
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,742
15
votes
0
answers
346
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,508
15
votes
1
answer
615
views
Exact Algorithm for edge labeling problem in DAG
I am implementing some system part of which requires some help. I am therefore framing it as a graph problem to make it domain independent.
Problem: We are given directed acyclic graph $G=(V,E)$. ...
- 23.3k
14
votes
0
answers
193
views
NP-Hardness of 4-cycle packing problem in complete bipartite digraph?
A directed complete bipartite graph is a bipartite graph where there is exactly one directed edge between any two vertices from its two different parts. In other words, it's an orientation of a ...
- 483
14
votes
0
answers
311
views
Categorical semantics for S5 modal logic?
Does anyone know where I can look to find out what the generally categorical semantics of S5 is?
For S4, the answer is well-known: we want a Cartesian closed category with a product-preserving ...
- 32.9k