10
The decision version of the DFA identification problem (find a possibly non-unique smallest DFA that is consistent with a set of given labeled examples) is NP-complete:
Input: Integer $k$ and sets $P, N \subseteq \Sigma^*$
Question: Is there a DFA $A$ with at most $k$ states such that $P \subseteq L(A)$ and $N \cap L(A) = \emptyset$. In other words $A$ ...
6
Minimizing deterministic Büchi automata is NP-complete, see Minimisation of Deterministic Parity and Buchi Automata and Relative Minimisation of Deterministic Finite Automata.
Deciding whether a coBüchi automaton is determinizable by pruning is also NP-complete, see Computing the Width of Non-deterministic Automata.
5
Notation: Let $P(\langle x_1,\dots,x_k\rangle)$ the set of degree $k$ curves that evaluates to $x_1,\dots,x_k\in\mathbb{F}^m$ at the first $k$ field elements in $\mathbb{F}$ and we will use just $P$ as a shorthand for this set. Let $S$ be any subset of $ \mathbb{F}^m$. Below, we assume
that multiplicity is taken into account when set cardinalities are ...
5
The best algorithm for 3-SAT now has numerical upper bound O(1.306995^n).
It is described in this paper:
Thomas Dueholm Hansen, Haim Kaplan, Or Zamir, Uri Zwick, Faster k-SAT algorithms using biased-PPSZ , 2019
Simply speaking, it adds bias to the PPSZ algorithm to let some literals have a higher, lower or equal probability to turn to some value.
In the ...
4
Here is another NP-complete variation of the DFA intersection non-emptiness problem.
(1) Given a list of DFA's and a number $n$ (in unary), does there exist a string of length at most $n$ that is accepted by all of the DFA's?
Also, here are two NP-complete variations of the DFA non-emptiness problem.
(2) Given a 2DFA and a number $n$ (in unary), does ...
4
Define the language $BACKPOINTER$ to have words of length $n+t\log n$, divided to $1+t$ parts, one of length $n$ and the rest of length $\log n$, by commas such that $BACKPOINTER=\{(x,p_1,\ldots,p_t)\mid x_{p_i}=1 \forall i\}$.
It should follow from some standard one-way communication complexity bound that $BACKPOINTER$ needs at least $t$ bits of memory ...
4
It essentially depends on what you mean by "evaluating this join". If you want to compute the whole table, then the $2^n$ blow-up is unavoidable, just because you need to store all these values.
However, given an acyclic query, you can compute the "semi-join" in time linear in the size of the data and linear in the size of the query. The semi-join is the ...
3
A nice question! Time to get Garey and Johnson off the shelf once again. Problem [AL2] in the problem list mentions the following: The nonemptiness problem for deterministic 2-way deterministic finite automata (2DFAs) over unary alphabet is NP-complete.
Zvi Galil: Hierarchies of complete problems. Acta Informat. 6, 77-88.
Another problem that comes to ...
3
Håstad, Jukna, and Pudlák used the sunflower lemma to prove lower bounds on depth-$3$ $AC^0$ circuits:
http://www.csc.kth.se/~johanh/topdowndepth3.pdf
This is also explained in Section 6.3 of the book of Jukna on extremal combinatorics, and in Section 11.3 of his book on boolean function complexity.
3
Razborov's lower bound on the size of monotone boolean circuits for the clique problem is an early application in TCS. A. A. Razborov, Some lower bounds for the monotone complexity of some Boolean functions, Soviet Math. Dokl. 31 (1985), 354-357. A good reference for learning about this is chapter 9 in Jukna's book "Boolean Function Complexity: Advances and ...
3
Sunflower lemma has applications in data structure lower bounds(as mentioned above). For eg. see:
Lower Bounds on Non-Adaptive Data Structures Maintaining Sets of Numbers, from Sunflowers.
3
The latter. The former is impossible for NP-complete languages by the nondeterministic time hierarchy theorem: assume for contradiction that $B$ is a language computable in nondeterministic time $p(n)$ such that every NP language reduces to it in time $q(n)$. Then
$$\mathrm{NP}\subseteq\mathrm{NTIME}(q(n)+p(q(n)))
\subsetneq\mathrm{NTIME}((q(n)+p(q(n)))n)\...
2
Finding the shortest synchronizing word for a DFA, if one exists (or more properly testing the existence of a synchronizing word shorter than a parameter $k$) is NP-complete.
See my paper: Eppstein, David (1990), "Reset sequences for monotonic automata", SIAM J. Comput. 19 (3): 500–510, doi:10.1137/0219033, Theorem 8.
2
As mentioned above: question answered by reference to FO(TC) games presented in Finite Model Theory by Ebbinghaus and Flum.
1
It is the latter, i.e. there is a polynomial $q_L$ for every language $L$. A clear way to see this is in the proof of the Cook-Levin Theorem.
The theorem requires the construction of a polynomial size-bounded tableau depending on the time bound for a NTM deciding $L$. The time bound changes depending on the language, of course. So the tableau used in the ...
1
If LOGLOG = NLOGLOG then LOG = NLOG. See more in:
https://www.sciencedirect.com/science/article/pii/0304397590900086
and therefore, your question is still an unsolved problem.
Only top voted, non community-wiki answers of a minimum length are eligible
