Towards average-case complexity analysis of NP optimization problems
Rainer Schuler, Osamu Watanabe · 2002
For the worst-case complexity measure, if P=NP, then P=OptP, i.e., all NP optimization problems are polynomial-time solvable. On the other hand, it is not clear whether a similar relation holds when considering average-case complexity. We investigate the relationship between the complexity of NP decision problems and that of NP optimization problems under polynomial-time computable distributions, and study what makes them (seemingly) different. It is shown that the difference between P/sub tt//sup NP/-samplable and P/sup NP/-samplable distributions is crucial.