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, (15[1])a technique known as “universal search”. This scientist pioneered a method of reduction between distributional problems to introduce the complexity class distNP and the concept of average-case complexity. This man is the second namesake of a theorem whose typical proof defines a tableau (15[1])that encodes the entire computation history of an accepting (*) Turing machine. That theorem, named for this man and an American, was used by Richard Karp to produce a list (10[1])of 21 problems. (-5[1])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