# Tag Info

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 ...
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.

### 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 ...
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 ...

### 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. ...

### 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 ...

### 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 ...

### 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 ...

### 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 ...
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/...

### 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 ...

### 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 ...

### 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 ...

### 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 ...
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 ...

### 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 ...

### 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 ...

### 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) ...

### 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 ...
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 ...
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 ...

### 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 ...

### 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 ...

### 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 ...

### 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 ...

### 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 ...