New answers tagged


No, the variant is in P: for each element $x_i \in X$ find the set $A_{x_i}$ of triples "reachable" from $x_i$: start with all triples containing $x_i$ $A_{x_i} = \{ (x, y, z) \mid x = x_i \}$ iteratively add to $A_{x_i}$ all triples that share at least one element with all triples already in $A$ check if $E \setminus A_{x_i}$ is a solution and also for ...


Assuming $x(e)=1$ in Condition 2, the problem is NP-complete. Clearly it is in NP. We show NP-hardness by reduction from Subset Sum: Lemma 1. The problem is NP-hard. Proof. The proof is by the following reduction from Subset Sum. Given a Subset-Sum input $(y, T)$, where $y=(y_1, y_2, \ldots, y_n)$ is a sequence of integers, and $T$ is the target, the ...


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.


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 ...

Top 50 recent answers are included