Various minimization problems associated with the diagnosis of systems represented by directed graphs are shown to be NP-complete. These problems include () finding the minimum number of test points, test connections and blocking gates on a SEC graph (single entry single exit connected acyclic graph), respectively, to make it distinguishable, and () finding a test set with the minimum number of tests to locate a faulty vertex on a SEC graph with test points, test connections and blocking gates attached, respectively. The NP-completeness results indicate that these problems are all intractable in the sense that it is most unlikely that some algorithm can solve them in polynomial time of the problem size.