# Tag Info

Accepted

### Are there any open problems left about DFAs?

Here is one problem described in the book "A second course in formal languages and automata theory" by Shallit. Let $u$ and $v$ be two distinct words with $|u|=|v|=n$. What is the size of the ...
• 7,578

### Are there any open problems left about DFAs?

Here's a very simple decision problem about DFA's. Given a DFA M, does M accept the base-2 representation of at least one prime number? Currently, we don't even know if this problem is recursively ...
• 6,898

### Are there any open problems left about DFAs?

The Černý conjecture is still open and important. It is about DFAs that have a synchronizing word (a word with the property that two copies of the automaton started in different states always end up ...
• 50.2k

### Are there any open problems left about DFAs?

Title: Intersection non-emptiness for two DFA's Description: Given two DFA's $D_1$ and $D_2$, does there exist a string $x$ such that $D_1$ and $D_2$ both accept $x$? Open Problem: Can we solve ...
• 4,900

### Are there any open problems left about DFAs?

I want to point out the another research problem, which concerns the interplay of very basic concepts about DFAs. It is well known that any n-state NFA can be converted into an equivalent DFA having ...
• 5,424
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 ...
• 35.7k
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.
• 2,718

### 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 ...
• 3,094

### Are there any open problems left about DFAs?

Minimal cover automata is one of a related stuff. Given a finite language $L$, we can obtain a minimal DFA for $L$. But if we relax requirements of DFA we can find smaller ones. We know that longest ...
• 3,420
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 ...
• 5,225

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

### Are there any open problems left about DFAs?

Here's an open problem relating DFA and machine learning theory: are uniformly random (random transitions and accept/reject behavior) DFA learnable in the PAC model? Note: we think arbitrary DFA are ...
• 11.7k

### 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 ...
• 26.3k

### 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. ...
• 7,042

### 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 ...
• 14.1k

### 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 ...
• 515
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/...
• 9,556

### 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 ...
• 5,963

### 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 ...
• 3,816

### 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) ...
• 4,721

### 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 ...
• 2,789
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 ...
• 9,378
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 ...
• 10.3k
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 ...