(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 ...