$(30)$ A language $A$ is disjunctively self$-$reducible if there is a polynomial$-$time com$-$

putable function $f$ with the following properties.

For each xin$\{0,1{\}}^{**},f(x)$ is one of the following.

"accept"

"reject"

a set of strings $Q_x$sube$\{0,1{\}}^{?}<mi>|</mi><mi>x</mi><mi>|</mi>$

For each xin$\{0,1{\}}^{**},$

xinALongleftrightarrow$[f(x)=$ accept$]or$

is a set $Q_x$ that satisfies $.$

Note that

On an input $x,$ the function $f$ either tells us to "accept" $x$ or "reject" $x,$ or it outputs

a set $Q_x$ of queries about shorter strings. In the latter case, $x$ is in $A$ if and only if at

least one of the queries is in $A.$

Let DSR be the class of all disjunctively self$-$reducible languages.

$($a$)$ Show that SUBSET$-$SUM $in$ DSR and CLIQUE $in$ DSR$.$

$($b$)$ Show that DSRsubeNP.