18 votes
Accepted

List of number theoretic or algebraic problems in various complexity classes

Algebraic geometry Noether's Normalization Lemma (NNL) for explicit varieties is currently only known to be in $\mathsf{EXPSPACE}$ (like general NNL), but is conjectured to be in $\mathsf{P}$ (and is ...
user avatar
16 votes
Accepted

Is optimally solving the n×n×n Rubik's Cube NP-hard?

One of my papers was just posted to arXiv and addresses this question: optimally solving the Rubik's Cube is NP-complete.
user avatar
15 votes

Integer linear programming in logarithmic number of variables

I can only give a partial answer to this question. A result by Lenstra (later improved by Kannan, and Frank and Tardos) states that ILP with $k$ variables can be solved in time $k^{O(k)}$ (times a ...
user avatar
13 votes
Accepted

Is it still open to determine the complexity of computing the treewidth of planar graphs?

As far as I know the NP-completeness of computing the treewidth of a planar graph is still open. The most recent reference I know is a survey by Bodlaender from 2012 called `Fixed-Parameter ...
user avatar
  • 5,225
13 votes

Does Memcomputing really solve an NP-complete problem?

I feel this has been answered sufficiently in the comments, so to just sum everything up: The authors do not claim P=NP, which is a statement about deterministic and nondeterministic Turing machines. ...
user avatar
  • 7,090
12 votes

Approximating the sign rank of a matrix

Recent work by Alon, Moran, and Yehudayoff gives an $O(n/\log n)$ approximation algorithm. Let $d$ be the VC-dimension of a sign matrix $S$. The idea is that there exists an efficiently computable ...
user avatar
12 votes

Major unsolved problems in theoretical computer science?

Summary Table for Answers Open Problems Matrix Multiplication: Can multiplication of $n$ by $n$ matrices be done in $O(n^2)$ operations? Graph Isomorphism: Is Graph Isomorphism in P? Factoring: Is ...
12 votes

Problems not known to be PSPACE-complete

Retrograde Chess. It is $PSPACE$-complete if you are allowed to have arbitrarily many kings and none of them can be in check at any time. If no (or only one per player) kings are allowed, it is known ...
user avatar
11 votes

Problems not known to be PSPACE-complete

I'm not sure if this fits your notion of restriction, but here goes. The "Minimum QBF-oracle Circuit Size Problem": given the truth table of a Boolean function and parameter k, is there a circuit of ...
user avatar
10 votes
Accepted

Massive online collaboration for solving open problem in theoretical computer science

Polymath projects seems to succeed when a breakthrough happens, and one is trying to optimize the result of the breakthrough or come up with simpler or better proof. See https://en.wikipedia.org/wiki/...
user avatar
10 votes

Research problems in communication complexity

I'll start with answers to your general questions, then give one nice open problem with applications towards circuit complexity. It's hard to say what areas a new communication complexity researcher ...
user avatar
10 votes

Are there any interesting open questions having to do with submodularity, specially in the intersection of theoretical machine learning?

There are many open algorithmic problems. All problems below (other than the last bullet) are NP-hard, so we are interested in the best approximation ratio we can achieve in polynomial time. The ...
user avatar
  • 14.1k
9 votes

What is the asymptotic time complexity of the number of steps of "Half Or Triple Plus One" ( HOTPO)?

By request, two facts that are known and seem somewhat related to your question. As a lower bound: infinitely many integers $n$ take time $\Omega(\log n)$. Applegate and Lagarias. As a sort of an ...
user avatar
8 votes

Major unsolved problems in theoretical computer science?

It seems strange to me that almost all the answers are about computational complexity, while the question asks for problems in all computer science. To counter-balance a little bit: Decidability of ...
8 votes
Accepted

Learning with (Signed) Errors

(wow! after three years of time passing, this is now easy to answer. funny how that goes! --Daniel) This "Learning with (Signed) Errors" (LWSE) problem, as invented-and-stated above by me (three ...
user avatar
  • 5,973
8 votes

Does there exist a hardest DCFL?

An identical homomorphism characterization of DCFL does not seem to be possible. The following is extracted from Greibach's original paper. We show that every context-free language can be expressed ...
user avatar
8 votes

Does there exist a hardest DCFL?

There actually is a hardest DCFL, which is a deterministic version of Greibach's; it was introduced by Sudborough in 78 in On deterministic context-free languages, multihead automata, and the ...
user avatar
8 votes

Does there exist a hardest DCFL?

The paper J.-M. Autebert, Une note sur le cylindre des langages déterministes, Theoretical Computer Science 8 (1979), 395-399 gives a short proof of the following result (credited to Greibach) ...
user avatar
  • 4,721
7 votes

Are there any open problems left about DFAs?

How many regular languages are there whose minimal DFA has exactly $n$ states? It seems to me that a closed-form formula should exist, but none is known. Some asymptotic bounds are known: On the ...
user avatar
  • 2,789
7 votes
Accepted

What is the asymptotic time complexity of the number of steps of "Half Or Triple Plus One" ( HOTPO)?

First, as the conjecture is still open, we can't say if $f$ is even defined for every $n$. Let's assume that if $f(n)=\infty$, then the algorithm is required to output $-1$. In 1972 Conway showed ...
user avatar
  • 9,378
7 votes
Accepted

List of (unsolved) complexity problems arising from PL

Pippenger's (1) from 1996 shows that (under some assumptions) strict (CBV) functional programming languages are asympotically slower than imperative languages. It is open whether Pippenger's result ...
user avatar
6 votes

Research problems in communication complexity

Several long-standing key open problems are in the Kushilevitz and Nisan textbook (see also the list of errata which mentions that Open Problem 8.6 was solved by Dietzfelbinger). Razborov's 2011 ...
user avatar
6 votes

Does Memcomputing really solve an NP-complete problem?

I would like to add some additional information to Daniel Primosch's answer from above. The figure with the results from the paper he cited is accurate. We got in touch with the authors a while back ...
user avatar
  • 69
5 votes

Are there any open problems left about DFAs?

Here is a DFA-related question I'd posted here before, and it's still open as far as I know: Fix an integer $n$ and alphabet $\Sigma=\{0,1\}$. Define $DFA(n)$ to be the collection of all finite-state ...
user avatar
  • 10.1k
5 votes

What is the "nearest" problem to the Collatz conjecture that has been successfully resolved?

Consider the function $T: \mathbb N \rightarrow \mathbb N$, where $T(n)=n/2$ when $n$ is even and $T(n)=n+1$ when $n$ is odd. Then it is known that for any $n \in \mathbb N$, there exists a $k \in \...
user avatar
5 votes

Problems not known to be PSPACE-complete

The following problem matches the requirement somehow twofold... Containment of regular expressions, that is, testing whether the language of a regular expressions $r$ is contained in the language of ...
user avatar
  • 1,377
4 votes

List of number theoretic or algebraic problems in various complexity classes

Adding a few more with emphasis on Galois theory and computational Galois theory (see related question on cs.SE): The computational complexity of determining if a given monic irreducible polynomial ...
user avatar
  • 571
4 votes

Major unsolved problems in theoretical computer science?

Getting an O(1) factor approximation algorithm in polytime for the Maximum Independent Set of Rectangles. This is one of the biggest open problems in Computational Geometry. Recently, Anna Adamaszek ...
4 votes

"Refined" list of open problems in TCS

There is a list of open problems in computational geometry. It is edited and maintained by Demaine, Mitchell, and O'Rourke.
user avatar
3 votes

Status of Cerny Conjecture?

see ArXiv: 1405.2435 cs.FL "The length of a minimal synchronizing word and the \v{C}erny conjecture" with the story of study https://arxiv.org/pdf/1405.2435.pdf
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible