66
Michael Soltys and I have succeeded in proving that the problem of determining whether a string can be written as a square shuffle is NP complete. This applies even over a finite alphabet with only $7$ distinct symbols, although our proof is written for an alphabet with $9$ symbols. This question is still open for smaller alphabets, say with only $2$ ...
56
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 smallest DFA that accepts $u$ but rejects $v$, or vice versa?
Robson, in his paper "Separating strings with small automata" in 1989 proved an upper bound $O(n^{...
42
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 solvable.
If it is recursively solvable, and we had an algorithm for it, we could resolve the longstanding open problem about whether there are any Fermat ...
39
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 in the same state as each other after both processing the word), and asks whether (for $n$-state automata) the length of the shortest such word is always at most ...
24
Here's what I know about the girth problem in undirected unweighted graphs.
First of all, if the girth is even, you can determine it in $O(n^2)$ time- this is an old result of Itai and Rodeh (A. Itai and M. Rodeh. Finding a minimum circuit in a graph. SIAM J. Computing, 7(4):413–423, 1978.). The idea there is: for each vertex in the graph, start a BFS until ...
23
Some of you are probably aware of this, but the 17 x 17 coloring problem has been solved by Bernd Steinbach and Christian Posthoff. See Gasarch's blog post here.
23
I think the overall goal of PL theory is to lower the cost of
large-scale programming by way of improving programming languages and
the techincal ecosystem wherein languages are used.
Here are some high-level, somewhat vague descriptions of PL research
areas that have received sustained attention, and will probably
continue to do so for a while.
Most ...
22
An extended comment:
Collatz-like sequences can be computed by small Turing machines having few symbols and states. In "Small Turing machines and generalized busy beaver competition" by P. Michel (2004), there is a nice table that positions Collatz-like problems between decidable TMs (for which the halting problem is decidable) and Universal TMs.
There ...
21
Are NP-completeness in the sense of Cook and NP-completeness in the sense of Karp different concepts, assuming P $\neq$ NP?
20
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 at most $2^n$ states. This is best possible in the worst case, in the sense that there are regular languages of nondeterministic state complexity n (i.e., the ...
20
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 intersection non-emptiness for two DFA's in $o(n^2)$ time?
If we could solve this problem in $O(n^{\delta})$ time where $\delta$ < 2, then the strong ...
18
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 in $\mathsf{P}$ assuming that PIT can be black-box derandomized). Update 4/18/18: It was recently shown that for the variety $\overline{\mathsf{VP}}$ it is in $...
16
Is there an algorithm to compute the generalized star-height of a given regular language?
See http://en.wikipedia.org/wiki/Generalized_star_height_problem
Generalized regular expressions are defined like regular expressions, but they allow the complement operator. The generalized star height (gsh) of a regular language is the minimum nesting depth of ...
15
One of my papers was just posted to arXiv and addresses this question: optimally solving the Rubik's Cube is NP-complete.
15
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 polynomial in the size of the ILP). Therefore, ILP is in P when the number of variables is $O(\log n/\log\log n)$. I am not sure if a $2^{O(k)}$ algorithm is ...
14
The conjecture fails over $\mathbb{F}_2$. Look at $M(x, y) = \langle x, y \rangle \bmod 2$, and $x, y \in \{0, 1\}^n$. The communication complexity is $\Omega(n)$, but the rank of $M$ over $\mathbb{F}_2$ is $n$, by the linearity of inner product.
13
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 Tractability of Treewidth and Pathwidth' that appeared in the festschrift for Mike Fellows' 65th birthday. The problem is listed in the conclusion of the survey.
12
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 Factoring in P?
BPP vs. P: Is BPP = P?
Simplex: Is there a pivoting rule for the simplex algorithm that yields worst-case polynomial running time?
ETH: Is the ...
12
You can easily check this in linear time, since a graph has edge
connectivity at least $n/2$ if and only if its minimum degree is at
least $n/2$. You already argued for the “only if” part. Consider now a
graph where every vertex has degree at least $n/2$ and a cut that
divides the graph into two vertex sets $X$ and $\bar X$ with $x := |X|
\leq n/2$. A vertex ...
12
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 matrix $M$ with sign pattern $S$ such that $\mathrm{rank}\ M = O(n^{1-1/d})$;
the sign rank of $S$ is at least $d$.
So the algorithm computes $M$ and outputs ...
12
You can check the following paper:
Translational lemmas, polynomial time, and $ (\log n)^j$-space by Ronald V. Book (1976).
Figures 1 and 2 in the paper give the summary of what is known and what is unknown.
I put Theorem 3.10 in the paper here:
$ DTIME(poly(n)) \neq DSPACE(poly(\log n)) $;
for every $ j \geq 1 $, $ DTIME(n^j) \neq DSPACE(poly(\log n)) $...
12
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 word in a finite language $L$ has length $l$. Define DFCA as a DFA which accepts only words in $L$ or possibly words which are longer than $l$. Then this DFCA ...
12
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 not learnable b/c of cryptographic hardness results. For random DFA, we only have SQ lower bounds, which are not as strong.
12
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 that there are positions that require exponential moves, but the problem is only known to be $NP$-hard.
http://arxiv.org/abs/1409.1530
https://mathoverflow....
11
The solution that Sam Buss and I proposed in November 2012 (showing that unshuffling a square in NP-hard by a reduction from 3-Partition) is now a published article in the Journal of Computer System Sciences:
http://www.sciencedirect.com/science/article/pii/S002200001300189X
11
Romeo Rizzi and Stéphane Vialette prove that recognizing square strings is NP-complete in their 2013 paper "On Recognizing Words That Are Squares for the Shuffle Product", by reduction from the longest binary subsequence problem. They state that the complexity of unshuffling a binary strings is still open.
An even simpler proof that finding non-nested ...
answered Jun 24 '13 at 17:06
Mohammad Al-Turkistany
19.6k4 gold badges51 silver badges134 bronze badges
11
I'll take a shot at your first question:
Are there examples of natural function families that quantum computers can learn faster than classical computers given cryptographic assumptions?
Well, it depends on the exact model and the resource being minimized. One option is to compare the sample complexity (for distribution-independent PAC learning) of the ...
11
Let me list some assumptions which limit the programming language research. These are hard to break away from because they feel like they are an essential part of what programming languages are about, or because exploring alternatives would be "not programming language design anymore". With each assumption I list its limiting effects.
Programs are syntactic ...
11
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 size at most k computing the function over the basis AND, OR, NOT, and QBF? (A QBF gate interprets its input string as a fully quantified Boolean formula F, ...
10
You might be interested in Scott Aaronson's talk "Has There Been Progress on the P vs. NP Question?" (earlier version)
Only top voted, non community-wiki answers of a minimum length are eligible
