# Interesting Research Problems

I have been thinking of interesting problems that can be researched for a long time, that I haven’t looked into much (or don’t have the time to do so) but have a healthy interest in understanding. If you would like to collaborate on one, any, or a related problem to one listed here, feel free to contact me.

1. Automata Theory

1. In the NFA to DFA transformation, we may have an exponential necessary increase in the number of states in the corresponding DFA (and there are explicit NFA constructions to guarantee this increase). What is the average/expected number in general? [Added Oct. 11, 2016]
2. In the NFA to DFA transformation, is there a polynomial-time algorithm to compute the number of states that will be produced for the DFA, without having to compute the DFA itself? [Added Oct. 11, 2016]
3. The number of strings of length ${n}$ that can be generated by a given unambiguous (i.e., every string in the grammar’s language only has 1 leftmost derivation) context-free grammar can be determined in polynomial time, with dynamic programming. What about for inherently ambiguous languages (i.e., every grammar is ambiguous)? [Added Oct. 13, 2016]

2. Fun and Games

1. What is the computational complexity of DiscoZoo? You are given an ${n \times n}$ grid and a list of shapes, with known patterns, as well as how many of each are inside the grid. The shapes are not oriented, rotated, or modified in any way. Your task is to find the fewest moves required to uncover all the shapes by selecting individual squares; doing so will reveal if a pattern contains that square (and remains known), and uncovers a “blank” otherwise. The patterns are not allowed to overlap (i.e., at most one pattern occupies a given square). An obvious upper-bound is ${n^2}$, but is it possible to do better? If not in the general case, what cases give interesting bounds? [Added Oct. 11, 2016]
2. What is the computational complexity of Guitar Hero (or any rhythm game)? There are many ways of formulating the question, such as (1) formulating a decision problem to see if it is possible to get above a certain score, (2) the minimum amount of interaction among ${k}$ players via star power to achieve a score, (3) the maximum number of notes missed to pass a given song, (4) are there any interesting generalizations of the game, etc. All of these I believe can be solved with dynamic programming in polynomial time, but I haven’t given much thought to it. [Added Oct. 13, 2016]

3. Graph Theory

1. A unicyclic graph is one that contains exactly 1 cycle. The number of spanning trees can be computed in polynomial time, due to a number of methods. Can the number of unicyclic spanning subgraphs of a graph be computed as efficiently? This has numerous applications to network reliability. [Added Oct. 13, 2016]

4. Network Reliability

1. Is there a closed formula for the reliability polynomial of the complete graph ${K_n}$? A recursive formula is:

$\displaystyle Rel(K_n; p) = 1- \sum_{j=1}^{n-1} {n-1 \choose j-1} Rel(K_j; p)(1-p)^{j(n-j)}.$

1. You are given a list of ${n}$ digits in base ${b}$. What is ${\max\{p_1 \times \cdots \times p_k\}}$ where the ${p_i}$ are concatenations of the ${n}$ digits (and partition the input digits)? [Added Oct. 11, 2016]
2. Given a range of integers ${[a, b]}$, what is the probability that for a given pair of integers ${(x, y) \in [a, b]}$ in the range (written in binary) that XORing, ANDing, or ORing the bitwise representations of ${x, y}$ remains in ${[a, b]}$? [Added Oct. 11, 2016]