Алгоритмика на связи!

В 1976 году премия Тюринга была присуждена вновь сразу двум ученым Дану Скотту и Майку Рабину за совместную «за работу „Finite Automata and Their Decision Problem“, в которой вводится понятие недетерминированных конечных автоматов, ставших несомненно полезной концепцией. Их труд стал постоянным источником вдохновения для дальнейшей работы в этой области». Недетерминированные конечные автоматы являются ключевым понятием в теории сложности вычислений, где с их помощью описывается класс NP.