Besonderhede van voorbeeld: -7442931702710331276

English

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.[1] 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.[2] Along with Blum, Floyd, Rivest, and Tarjan, he described median of medians, the first worst-case optimal selection algorithm.[3]

Spanish

Los Certificados de Pratt, pruebas cortas de la primalidad de un número, demostraron en una manera práctica que la primalidad puede ser eficientemente verificada, colocando el problema de la Prueba de primalidad en la clase de complejidad NP y proporcionando la primera evidencia fuerte de que el problema no es co-NP-completo.[1] El Algoritmo Knuth-Morris-Pratt, el cual Pratt diseñó en el principio de los 1970s junto con su compañero profesor en Stanford Donald Knuth e independientemente de Morris, es todavía el algoritmo de búsqueda de subcadenas general más eficaz conocido hoy.[2] Junto con Blum, Floyd, Rivest, y Tarjan, describió median de medians, el primer algoritmo de selección[3] óptimo en el peor-caso.