NPSchwer

NP-schwer, or NP-hard, is a classification in computational complexity theory used to describe problems that are at least as hard as the hardest problems in the class NP. A problem is NP-hard if every problem in NP can be transformed into it by a polynomial-time many-one reduction. NP-hardness does not require the problem itself to be a decision problem in NP; some NP-hard problems may be optimization problems or even undecidable.

In relation to NP-completeness, all NP-complete problems are NP-hard, but not all NP-hard problems are NP-complete. NP-complete problems are those that are both in NP and NP-hard. If any NP-hard problem could be solved in polynomial time, then every problem in NP could be solved in polynomial time (i.e., P = NP).

Common examples of NP-hard (or NP-complete) problems include the SAT problem (in its decision form) and many combinatorial optimization problems such as the traveling salesman problem (as an optimization version) and the subset-sum problem (in its decision form). These problems are used in reductions to establish the hardness of other problems and to study limits on efficient computation and approximability.

The term NP-Schwer is used primarily in German-language literature, where "schwer" translates to "hard." The concept is central to reduction-based proofs of hardness and to discussions about the limits of efficient computation and the practical boundaries of problem-solving in computer science.