74
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$ ...
59
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^{...
46
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 ...
42
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 ...
25
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 ...
21
Are NP-completeness in the sense of Cook and NP-completeness in the sense of Karp different concepts, assuming P $\neq$ NP?
21
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 ...
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 ...
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
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 ...
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
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
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 ...
12
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
12
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
20.1k4 gold badges55 silver badges138 bronze badges
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
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
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
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
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
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 following are just a sample:
Given a non-negative submodular function on a universe $U$, find a set $A$ of size at most $k$ maximizing $f(A)$. The best known ...
10
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 should delve into, since easy problems have likely been solved already, and harder problems are hard ;) One suggestion is to take known communication lower ...
10
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/Polymath_Project#Problems_solved. As such, you would have to pick a problem of this nature in CS. The only one that comes immediately to mind is improving the ...
9
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 upper bound: $\Omega(N^c)$ positive integers bounded by $N$ reach $1$ in finite time, where $c \approx 0.84$. Krasikov and Lagarias.
Hopefully you have read ...
9
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.
The authors propose a model of computation that they claim to show is equivalent in power to nondeterministic Turing machines.
The authors construct physical ...
Only top voted, non community-wiki answers of a minimum length are eligible
