Parallel self-reducibility

The authors examine the relationship between the complexity of solving a decision problem with that of solving a search problem. In particular, if they are given a solution for a decision problem in the form of an oracle, they consider the difficulty of finding evidence supporting the decision. For example, suppose they have an oracle which, when given a graph, indicates whether that graph has a Hamilton cycle (HC). The authors goal is to find a Hamilton cycle in a graph, thus proving it has one. After defining their problems using a relational model they show that if any NP-complete problem is self-reducible in parallel, then all NP-complete problems are. They also show that all P-complete problems have parallel self-reductions. Under the (unlikely) assumption that NP=co -NP, it is shown that NP-complete problems can be self-reduced. However, probabilism can be shown to help: any NP-complete problem has a randomized parallel self-reduction. Finally, natural evidence for an NP problem is discussed