Strong NP-completeness: Revision history

Jump to navigation Jump to search
Template:FlatlistExternal tools:

Template:Endflatlist

For any version listed below, click on its date to view it. For more help, see Help:Page history and Help:Edit summary. (cur) = difference from current version, (prev) = difference from preceding version, m = minor edit, → = section edit, ← = automatic edit summary

29 May 2025

  • curprev 16:1316:13, 29 May 2025 imported>Hbecker.inf 4,696 bytes +4,696 The paragraph about reduction is imprecise to the point of being wrong. What is called and used as a polynomial reduction in NP-hardness proofs does not meet the necessary bar to prove STRONG NP-hardness. Otherwise, the proof of 3SAT to Subset-Sum in Sipser would prove subset-sum to be a Strongly NP-hard problem.
Retrieved from "http://debianws.lexgopc.com/wiki143/index.php?title=Strong_NP-completeness"