Linked Questions
12 questions linked to/from Are there any open problems left about DFAs?
103
votes
15
answers
11k
views
A simple decision problem whose decidability is not known
I am preparing for a talk aimed at undergraduate math majors, and as part of it, I am considering discussing the concept of decidability. I want to give an example of a problem that we do not ...
- 11.9k
55
votes
7
answers
4k
views
For which problems in P is it easier to verify the result than to find it?
For (search versions) of NP-complete problems, verifying a solution is clearly easier than finding it, since the verification can be done in polynomial time, while finding a witness takes (probably) ...
- 11.3k
26
votes
4
answers
2k
views
Separating Logspace from Polynomial time
It is clear that any problem that is decidable in deterministic logspace ($L$) runs in at most polynomial time ($P$). There is a wealth of complexity classes between $L$ and $P$. Examples include $NL$,...
- 10.6k
27
votes
1
answer
2k
views
Deciding emptiness of intersection of regular languages in subquadratic time
Let $L_1,L_2$ be two regular languages given by NFAs $M_1,M_2$ as input.
Assume we would like to check whether $L_1\cap L_2\neq \emptyset$. This can clearly be done by a quadratic algorithm which ...
- 9,438
20
votes
1
answer
3k
views
What is the number of languages accepted by a DFA of size $n$?
The question is simple and direct: For a fixed $n$, how many (different) languages are accepted by a DFA of size $n$ (i.e. $n$ states)? I will formally state this:
Define a DFA as $(Q,\Sigma,\delta,...
- 1,406
29
votes
2
answers
2k
views
How many DFAs accept two given strings?
Fix an integer $n$ and alphabet $\Sigma=\{0,1\}$. Define $DFA(n)$ to be the collection of all finite-state automata on $n$ states with starting state 1. We are considering all DFAs (not just connected,...
- 10.4k
11
votes
2
answers
347
views
Separating lists of words
There is an open problem in formal languages known as the Separating Problem; which is briefly stated as given two distinct strings of length $n$, how large of a DFA is required to "separate"...
- 389
18
votes
2
answers
499
views
Separating words with random DFAs
One of the interesting open problems about DFAs listed in Are there any open problems left about DFAs? is the size of a DFA required to separate two strings of length $n$. I am curious if there any ...
- 3,243
9
votes
1
answer
489
views
Formalizing the "no formula for primes" intuition
I was trying to formalize the intuition is that there is no formula for primes, and this is my best attempt:
Conjecture: There is no $O(n^2)$ expected time randomized algorithm to generate $\ge n$-...
- 3,243
8
votes
1
answer
327
views
Two DFA intersection emptiness connections to SETH & L vs P
(re "fine grained complexity") Wehar has proved that
Two DFA intersection emptiness in $O(n^{2-\epsilon})$ time → SETH false.
does anyone see any particular key proof difficulty, challenge, ...
- 11k
-2
votes
1
answer
315
views
Finding research problem for PhD(TCS)? [closed]
I am a theoratical computer science PhD student.
I am wanted some suggestion in how to find research problem for PhD research. I have supervisor and he has given me first problem. We had get progress ...
- 17
6
votes
1
answer
190
views
Separating words and graph isomorphism
I wonder if there are any known implications of Babai's recent quasi-polynomial time algorithm for Graph Isomorphism to separating words by DFA's.
In both cases the ultimate goal is to differentiate ...
- 13.9k