New answers tagged np-hardness
1
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 ...
5
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 ...
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.
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 ...
Top 50 recent answers are included
