Premium
Computational complexity of PERT problems
Author(s) -
Hagstrom Jane N.
Publication year - 1988
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230180206
Subject(s) - computational complexity theory , duration (music) , range (aeronautics) , mathematics , task (project management) , mathematical optimization , time complexity , cumulative distribution function , random variable , function (biology) , computer science , algorithm , statistics , probability density function , art , materials science , literature , management , evolutionary biology , economics , composite material , biology
Computational complexity results for two PERT problems are presented. A project is specified by precedence relations among tasks. Task durations are independent random variables with discrete, finite ranges. The following results are obtained: (1) computing a value of the cumulative distribution function of project duration is # P ‐complete, (2) computing the mean of the distribution is at least as hard, and (3) neither of the problems in (1) and (2) can be computed in time polynomial in the number of points in the range of the project duration unless P = NP.