๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

An NP-Complete Number-Theoretic Problem

โœ Scribed by Gurari, Eitan M.; Ibarra, Oscar H.

Book ID
121864548
Publisher
Association for Computing Machinery
Year
1979
Tongue
English
Weight
806 KB
Volume
26
Category
Article
ISSN
0004-5411

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

An NP-complete matching problem
An NP-complete matching problem
โœ David A. Plaisted; Samuel Zaks ๐Ÿ“‚ Article ๐Ÿ“… 1980 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 847 KB
Crossing Number is NP-Complete
Crossing Number is NP-Complete
โœ Garey, M. R.; Johnson, D. S. ๐Ÿ“‚ Article ๐Ÿ“… 1983 ๐Ÿ› Society for Industrial and Applied Mathematics โš– 528 KB
NP-complete scheduling problems
NP-complete scheduling problems
โœ J.D. Ullman ๐Ÿ“‚ Article ๐Ÿ“… 1975 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 423 KB

We show that the problem of finding an optimal schedule for a set of jobs is NPcomplete even in the following two restricted cases. (1) All jobs require one time unit. (2) All jobs require one or two time units, and there are only two processor resolving (in the negative a conjecture of R. L. Grah