Unanswered Questions

50
votes
0answers
2k views

more on PH in PP?

A recent question by Huck Bennett asking whether the class PH was contained in the class PP, received somewhat contradictory answers (all true, it seems). On one hand, several oracle results were ...
46
votes
0answers
1k views

Is there a gap amplification type of result for the Graph Isomorphism Problem?

Suppose $G_1$ and $G_2$ are two undirected graphs on vertex set $\{1, \dotsc, n\}$. The graphs are isomorphic if and only if there is a permutation $\Pi$ such that $G_1 = \Pi(G_2)$, or more formally, ...
40
votes
0answers
1k views

Can one amplify P=NP beyond P=PH?

In Descriptive Complexity, Immerman has Corollary 7.23. The following conditions are equivalent: 1. P = NP. 2. Over finite, ordered structures, FO(LFP) = SO. This can be thought of as ...
37
votes
0answers
742 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 ...
32
votes
0answers
544 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 ...
32
votes
0answers
590 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 = ...
28
votes
0answers
589 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 ...
24
votes
0answers
392 views

Is cubic complexity still the state of the art for LP?

According to D. den Hertog, Interior Point Approach to Linear, Quadratic and Convex Programming, 1994, a linear program with $n$ variables, $n$ constraints and precision $L$ is solvable in $O(n^3L)$ ...
24
votes
0answers
911 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\}$. ...
23
votes
0answers
590 views

Complexity of matrix powering

Let $M$ be a square integer matrix, and let $n$ be a positive integer. I am interested in the complexity of the following decision problem: Is the top-right entry of $M^n$ positive? Note that the ...
23
votes
0answers
360 views

Interesting algorithms in the formalization of the Feit-Thompson theorem?

It looks like George Gonthier and his collaborators have finished formalizing the Odd Order Theorem. In his earlier work on the Four Color Theorem, Gonthier invented a bunch of new algorithms ...
22
votes
0answers
272 views

Eilenberg's rational hiererchy of nonrational automata & languages — where is it now?

In the preface to his very influential books Automata, Languages and Machines (Volumes A, B), Samuel Eilenberg tantalizingly promised Volumes C and D dealing with "a hierarchy (called the rational ...
22
votes
0answers
417 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". ...
21
votes
0answers
297 views

Regularity Lemma for Sparse Graphs

Szemeredi's Regularity Lemma says that every dense graph can be approximated as a union of $O(1)$ many bipartite expander graphs. More accurately, there's a partition of most vertices into $O(1)$ sets ...
21
votes
0answers
237 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 ...

15 30 50 per page