| Article ID: | iaor20081933 |
| Country: | Belarus |
| Volume: | 51 |
| Issue: | 3 |
| Start Page Number: | 29 |
| End Page Number: | 31 |
| Publication Date: | May 2007 |
| Journal: | Doklady of the National Academy of Sciences of Belarus |
| Authors: | Kovalyov M. Ya., Barketau M.S. |
The product partition problem, which is natural modification of the well-known NP-Complete subset product problem, is considered. It is shown that the product partition problem is NP-complete in a strong sense. The product partition problem can be used to estimate the computational complexity of a wide range of problems including scheduling theory problems with item processing times linearly dependent on the start item processing time.