Abstract für Paper
Autor: Rainer Schuler and Osamu Watanabe
Nr.: 13
Monat/Jahr: November 1994
Abstract:
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(NP)-truthtable-samplable and P(NP)-samplable
distributions is crucial.
Kontaktadresse:
schuler@informatik.uni-ulm.de