A pruning procedure maps a Boolean circuit to a circuit on the same variables that accepts only satisfying assignments of the original.
Valiant and Vazirani give a pruning procedure that leaves exactly one satisfying assignment of every satisfiable circuit with probability $\Omega(1/n)$, where $n$ is the number of variables. Dell, ...
more >>>
Assume indistinguishability obfuscation (iO) and one-way functions, both secure against nonuniform polynomial-size adversaries. We show that no randomized polynomial-size pruning procedure isolates a witness with probability at least a/log L, for any constant a > 0, where L is the length of the circuit description. Dell, Kabanets, van Melkebeek, and ... more >>>