• Member for 10 years, 10 months
  • Last seen more than 2 years ago
What are the consequences of $\mathsf{L}^2 \subseteq \mathsf{P}$?
27 votes

$ \newcommand{\DSPACE}{\mathsf{DSPACE}} \newcommand{\L}{\mathsf{L}} \newcommand{\P}{\mathsf{P}} \newcommand{\DTIME}{\mathsf{DTIME}} $ $\L^2 \subseteq \P$ would refute the Exponential Time Hypothesis. ...

View answer
Finding the sparsest solution to a system of linear equations
4 votes

This problem is hard, in various settings. As stated in the other answers to this question, the problem is NP-complete over the integers. In signal processing, the matrix and the vectors have ...

View answer
Hardest problems to approximate
4 votes

The title of this question does not match the content. As stated in the comments, there are some NP optimization problems for which any polynomial time approximation algorithm implies P = NP. Maybe ...

View answer
Problems in $\text{PSPACE} \cap \text{Co-NP-Hard}$
3 votes

Like the Boolean Formula Isomorphism problem, the Group Equations Isomorphism problem is $\mathsf{coNP}$-hard and in $\mathsf{\Sigma_2P}$, for any fixed non-abelian group. See The Complexity of ...

View answer
How big is NSC^k?
2 votes

This is not an answer to your exact question, but perhaps you may find this helpful. You might have a slightly easier time finding results for the class of languages decided by nondeterministic $\...

View answer
In what class are randomized algorithms that err with exactly 25% chance?
1 votes

This is a partial answer; maybe it will inspire someone else to provide a better one. $\newcommand{\EBPP}{\mathsf{EBPP}}$ $\newcommand{\CP}{\mathsf{C}_=\mathsf{P}}$ Your class $\EBPP$ is a special ...

View answer