Первая попытка аксиоматического подхода к измерению трудности вычислений была сделана Рабином [3, 4], который аксиоматизировал ... - Большая Энциклопедия Нефти и Газа
Выдержка из книги
Лупанов О.Б.
Кибернетический сборник Выпуск11
Первая попытка аксиоматического подхода к измерению трудности вычислений была сделана Рабином [3, 4], который аксиоматизировал понятие меры на доказательствах и длины вычисления функции и получил некоторые начальные результаты для этих мер. Первое систематическое исследование одной специфической меры сложности вычислений и изучение соответствующих классов сложности принадлежит Хартманису и Стирнзу [5, 6], которые дали также название сложность вычислений этой новой области исследований. В докладе Кобхэма [7] обсуждалась важность исследования количественных аспектов вычисления и приводились некоторые дальнейшие, результаты.
![Первая попытка аксиоматического подхода к измерению трудности вычислений была сделана Рабином [3, 4], который аксиоматизировал понятие меры на доказательствах и длины вычисления функции и получил некоторые начальные результаты для этих мер. Первое систематическое исследование одной специфической меры сложности вычислений и изучение соответствующих классов сложности принадлежит Хартманису и Стирнзу [5, 6], которые дали также название сложность вычислений этой новой области исследований. В докладе Кобхэма [7] обсуждалась важность исследования количественных аспектов вычисления и приводились некоторые дальнейшие, результаты.](/pic/22178433rsUcOP0004396609.png)