Unanswered Questions

3,028 questions with no upvoted or accepted answers
47
votes
0answers
2k views

Monotone complexity of s-t connectivity

In the problem CONN, we obtain a directed $n$-vertex graph (encoded as a boolean string of $n^2$ bits, one for each potential edge), and want to decide whether there is a path between all $n^2$ pairs $...
46
votes
0answers
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 ...
33
votes
0answers
1k views

Is BPP= P known for ANY uniform model of computation?

Many believe that BPP $=$ P "should" hold for Turing machines. We even have some "witnesses" for this: otherwise some "strange" things would happen; see e.g. this paper by Implagliazzo and Wigderson. ...
32
votes
0answers
5k views

Combinatorics of Bellman-Ford or how to make cyclic graphs acyclic?

Roughly speaking, my question is: How costly is to make a cyclic graph acyclic while preserving all simple $s$-$t$ paths? Let $K_n$ be a complete undirected graph on vertices $\{0,1,\ldots,n+1\}$. (...
30
votes
0answers
729 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". ...
29
votes
0answers
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\...
28
votes
0answers
481 views

Adiabatic quantum computing with level crossings

Question. In adiabatic evolution, to ensure that the ground state high overlap with the unique ground state of the system (i.e. to achieve arbitrarily small error) using adiabatic theorems, it is ...
27
votes
0answers
685 views

Is Hankelability NP-hard?

I asked this question on SO on April 7 and added a bounty which has now expired but no poly time solution has been found yet. I am trying to write code to detect if a matrix is a permutation of a ...
26
votes
0answers
583 views

Rank mod 6 vs rank over the reals

Let $A$ be a boolean matrix (eg with $0,1$ entries). Assume that $A$ has rank $\le r$ both over $\mathbb{F}_2$ and over $\mathbb{F}_3$. Does this imply that $A$ has low rank over the reals? This seems ...
26
votes
0answers
1k views

Counting Isomorphism Types of Graphs

Polya's counting theorem leads to an algorithm for counting (precisely) the number of isomorphism types of graphs with $n$ vertices in $\exp (\sqrt n )$ steps. From Polya theorem you get a formula ...
23
votes
0answers
1k views

$\Delta = 57, d=2$ Moore Graph

I am looking into the last open question regarding the existence of Moore Graphs of diameter 2. A problem that has been open in combinatorics for more than 55 years. You may recall that Hoffman and ...
22
votes
0answers
446 views

Fine-grained complexity of BPP

If E does not have i.o.-$2^{o(n)}$ circuits, then P=BPP, but this does not tell us about the fine-grained containments between $\mathrm{Time}(n^a)$ and $\mathrm{BPTime}(n^b)$. Are there reasonable ...
22
votes
0answers
691 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
0answers
1k views

Exact algorithm for NAE-3SAT

The NAE-3SAT problem is to determine whether a given 3CNF formula has a satisfying assignment that gives each clause at least one false (and at least one true) literal. The problem is NP-complete. One ...
21
votes
0answers
267 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))$?

15 30 50 per page
1
2 3 4 5
202