63
votes
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
48
votes
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
44
votes
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
24
votes
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
20
votes
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
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 ...
- 35.7k
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.
- 2,718
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 ...
- 3,094
13
votes
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
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 ...
- 5,225
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 ...
- 18k
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
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
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 ...
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 ...
- 26.3k
11
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.
...
- 7,042
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 ...
- 14.1k
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 ...
- 515
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/...
- 9,556
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 ...
- 18k
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 ...
- 5,963
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 ...
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
...
- 3,816
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) ...
- 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 ...
- 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 ...
- 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 ...
- 10.3k
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 ...
- 18.7k
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 ...
- 10k
Only top scored, non community-wiki answers of a minimum length are eligible