(a): The main idea of the proof is to perform a depth-first tree-pruning procedure on the self-reducing tree of the instance x. Note that for the c-self-reducible set A, the self-reducing tree of x has the following properties:
- The depth of the tree is bounded by for some polynomial p.
- if and only if there exists a path from root x to a leaf of which all nodes are not in A.
Suppose we perform a depth-first search of the tree. Then, we can tell whether as follows: (1) if some node (e.g., a leaf) in the tree is found to be not in A, then the search halts and output NO or (2) if all nodes in the tree (or, all leaves in the tree) are found to be in A, then output YES. This search procedure, however, does not work in polynomial time as the tree may have as many as nodes. So, the tree-pruning procedure is to be applied.
Assume that for some sparse set S via a function g. Also assume that for some polynomial q. For each node y of the tree, let us attach the string g(y) to ...