Who introduced nondeterministic computation? I have two historical questions:


  Who first described nondeterministic computation?


I know that Cook described NP-complete problems, and 
that Edmonds proposed that P algorithms are "efficient" or "good" algorithms.  

I searched this Wikipedia article and 
skimmed "On the Computational Complexity of Algorithms," 
but couldn't find any reference to when nondeterministic computation was first discussed.


  What was the first reference to the class NP? Was it Cook's 1971 paper?
I have always seen the notion of nondeterminism in computation attributed to Michael Rabin and Dana Scott. They defined nondeterministic finite automata in their famous paper Finite Automata and Their Decision Problems, 1959. Rabin's Turing Award citation also suggests that Rabin and Scott introduced nondeterministic machines.