The complexity of identifying redundant and essential elements

Shlomo Moran, Yehoshua Perl

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


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

Original languageEnglish (US)
Pages (from-to)22-30
Number of pages9
JournalJournal of Algorithms
Issue number1
StatePublished - Mar 1981
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Control and Optimization
  • Computational Mathematics
  • Computational Theory and Mathematics


Dive into the research topics of 'The complexity of identifying redundant and essential elements'. Together they form a unique fingerprint.

Cite this