Question

Along with an Israeli scientist, this person introduced hard-core predicates to formalize the notion of the difficulty of inverting a one-way function; that result is named for Oded Goldreich and this person. This scientist developed an approach to run every Turing machine in parallel while making progress on each machine, a technique known as “universal search”. This scientist pioneered a method of reduction between distributional problems to introduce the complexity class distNP (-5[1])and the concept of average-case complexity. This man is the second namesake of a theorem whose typical proof defines a tableau that encodes the (15[1])entire computation history of an accepting (*) Turing machine. (10[1])That theorem, named for this man and an American, was used by Richard Karp to (10[1])produce a list of 21 (10[1])problems. For 10 points, give this Soviet-American scientist who names the theorem that SAT is NP-complete along with Stephen Cook. ■END■ (10[1])

Back to tossups