Advertisement
Published in:
1994 | OriginalPaper | Chapter
NP-Hard Problems
Authors : V. S. Tanaev, V. S. Gordon, Y. M. Shafransky
Published in: Scheduling Theory. Single-Stage Systems
Publisher: Springer Netherlands
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
This chapter establishes the NP-hardiness of a number of scheduling problems. To prove that a given Problem B is NP-hard, we use the following scheme. The decision Problem B’ corresponding to Problem B is formulated, and a Problem A is shown to be polynomially reducible to B’ where A is one of the standard problems, i.e., a decision problem known to be NP-complete. If Problem A is NP-complete in the strong sense, then sometimes it is shown to be pseudopolynomially reducible to Problem B’.