Cтраница 4
Мы видели, что ограничение ленты, требуемой для разрешения множества на любой из машин четырех типов, может служить мерой сложности проблемы разрешения. Для трех моделей это ведет к богатой иерархии классов ленточной сложности, представляющих различную степень трудности. [46]
Общее число таких операций, выполняемых в процессе построения, называется его простотой, хотя Лемуан полагал, что, возможно, более уместен термин мера сложности. Это определение близко связано с нашей современной идеей временной сложности алгоритма, хотя в работе Лемуана нет функциональной связи между размером исходной информации ( числом заданных точек и линий) для геометрического построения и его простотой. Безусловно, интерес Лемуана был направлен на улучшение исходных евклидовых построений, а не на развитие теории сложности вычислений. К сожалению, Лемуан не почувствовал важности доказательства, а возможно, просто не смог доказать, что определенное число операций было необходимо для данного построения, и, таким образом, идея о нижней оценке алгоритма ускользнула от него. [47]
Во втором разделе этой статьи мы постулировали два свойства, которыми должна обладать любая мера сложности вычислений, а затем мы получили несколько результатов о мерах сложности, используя только эти постулаты. [48]
В то же время следует также отметить, что многие специалисты в области применения вычислительных машин, возможно, гораздо более заинтересованы в результатах о специфических мерах сложности для специфических проблем. Тем не менее обрисованный выше подход достаточен, чтобы начать развивать общую теорию. [49]
Следовательно, чтобы определить некоторую меру сложности, нам нужен эффективный способ задания всевозможных вычислений или алгоритмов ( для вычисления частично рекурсивных функций), а мера сложности тогда будет показывать, сколько шагов требуется любому из этих алгоритмов, чтобы по данному значению аргумента вычислить соответствующее значение функции. [50]