The complexity of identifying redundant and essential elements

In many optimization problems a solution is a subset of optimum number of elements satisfying some desired property. An element is redundant if it does not belong to any solution of the problem. An element is essential if it belongs to every solution of the problem. We consider the complexity of indentifying redundant and essential elements in a sample of NP-Hard optimization problems. It is shown that these identification problems are also NP-Hard. The proofs are based on an analysis of the original reductions of Cook The complexity of theorem proving procedures, in “Proceedings, Third Annual Assoc. Comput. Mach. Symposium on Theory of Computing”, pp. 151–158, Assoc. Comput. Mach., New York 1971] and Karp Reducibility among combinational problems, in “Complexity of Computer Computations” (R. E. Miller and J. W. Thatcher, Eds.), pp. 85–104, Plenum, New York 1972].