The complexity of identifying redundant and essential elements

Shlomo Moran, Yehoshua Perl

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

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
Volume2
Issue number1
DOIs
StatePublished - Mar 1981
Externally publishedYes

All Science Journal Classification (ASJC) codes

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

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

Cite this