Unanswered Questions
338 questions with no upvoted or accepted answers
47
votes
0
answers
1k
views
Problem unsolvable in $2^{o(n)}$ on inputs with $n$ bits, assuming ETH?
If we assume the Exponential-Time Hypothesis, then there is no $2^{o(n)}$ algorithm for $n$-variable 3-SAT, and many other natural problems, such as 3-COLORING on graphs with $n$ vertices. Notice ...
CommunityBot
- 1
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
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
281
views
Does small circuits for a NP-complete problem contradict ETH?
The remarks of the Theorem 4 in the paper "On the complexity of circuit satisfiability" claims that: if circuit satisfiability (CktSat) problem can be decided by deterministic circuits of $2^{o(n)}$ ...
- 161
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
522
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
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
699
views
Does solving matrix multiplication in quadratic time imply that SETH is false?
I have a little conjecture that if you could perform matrix multiplication (or solve 3-clique) in $O(n^2 \log(n))$ time, then you could solve CNF-SAT in $O(2^{(1-\epsilon)n})$ time.
In other words, ...
- 5,167
14
votes
0
answers
494
views
DPLL and Lovász Local Lemma
Let $\varphi$ be a CNF formula. Suppose that each of $\varphi$'s clauses consist of exactly $t$ literals (and, moreover, all literals within one particular clause correspond to different variables). ...
- 21.8k
13
votes
0
answers
633
views
Recent progress on the next-to-shortest-path problem for directed graphs?
In the paper "Computing strictly-second shortest paths" (1997), Lalgudi and Papaefthymiou consider the following problem:
Let $G$ be a directed graph with edge-weighting $w$. Let $u,v$ be ...
CommunityBot
- 1
13
votes
0
answers
296
views
Which monotone DNFs are evasive?
A Boolean function $\phi$ on variables $X$ is evasive if every decision tree for $\phi$ has height $|X|$. In other words, for any strategy that picks variables of $X$ and asks for their value, an ...
- 9,838