Linked Questions

95
votes
15answers
10k 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 ...
52
votes
7answers
3k 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) ...
25
votes
4answers
1k 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$,...
25
votes
1answer
1k 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 ...
19
votes
1answer
2k 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,...
10
votes
2answers
218 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"...
9
votes
1answer
398 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$-...
8
votes
1answer
271 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, ...
15
votes
1answer
332 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 ...
-2
votes
1answer
268 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 ...
6
votes
1answer
153 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 ...