Major Contributions
A number of well-known algorithms bear Pratt's name. Pratt certificates, short proofs of the primality of a number, demonstrated in a practical way that primality can be efficiently verified, placing the primality testing problem in the complexity class NP and providing the first strong evidence that the problem is not co-NP-complete. The Knuth-Morris-Pratt algorithm, which Pratt designed in the early 1970s together with fellow Stanford professor Donald Knuth and independently from Morris, is still the most efficient general string searching algorithm known today. Along with Blum, Floyd, Rivest, and Tarjan, he described the first worst-case optimal selection algorithm.
Read more about this topic: Vaughan Pratt
Famous quotes containing the word major:
“Give me the keys. I feel for the common chord again,
Sliding by semi-tones till I sink to a minor,—yes,
And I blunt it into a ninth, and I stand on alien ground,
Surveying a while the heights I rolled from into the deep;
Which, hark, I have dared and done, for my resting-place is found,
The C Major of this life: so, now I will try to sleep.”
—Robert Browning (1812–1889)