In 1971, Stephen Cook and, working independently, Leonid Levin, proved that there exist practically relevant problems that are NP-complete – a landmark result in computational complexity theory.
Το 1971, ο Στίβεν κουκ και ο Λεονίντ Λιβάιν, που δούλευαν ανεξάρτητα, απέδειξαν ότι υπάρχουν πρακτικά σχετικά προβλήματα τα οποία είναι NP-πλήρης – ένα σημείο αναφοράς το οποίο είχε σαν αποτέλεσμα την θεωρία της πολυπλοκότητας.