Sensitivity of probabilistic results on algorithms for NP-complete problems to input distributions
J. Franco · ACM SIGACT News · 1985
The field of analysis of algorithms embodies three kinds of results : worst case, probabilistic results on deterministic algorithms and probabilistic results on randomized algorithms .In the case of worst cas e analysis an upper bound on some computational resource, usually time o r space, is sought for a particular algorithm or, in the case of optimization problems which are solved by approximation algorithms, an uppe r bound on the difference between the value of the optimal solution and th e value of the solution produced by a particular algorithm is sought .Worst case results are useful because they guarantee a level of performance .In the case of probabilistic analysis on deterministic algorithm s the use of some computational resource averaged over all possible input s or the probability that a resource requirement exceeds a given bound , usually a polynomial function of the input size, or the probability tha t an algorithm correctly solves a random input is sought [12] .Probabilistic results show how well algorithms perform on random inputs .Ofte n an algorithm with pessimistic worst case performance works very well o n random inputs ; such an algorithm might be useful in a practical sens e since so few inputs yield poor performance .Thus, probabilistic result s are a useful supplement to worst case results because they indicate th e performance one might expect to get in practice .Unfortunately, probabilistic results depend on the assumption of an input distribution o r model and as we will see can be rather sensitive to small changes in th e distribution .In the case of randomized algorithms [16] the results d o not depend on input distributions but on distributions associated wit h the computation process .Results are the same for any input so randomized algorithms give predictable performance regardless of inpu t distribution .