хартманис и машины тьюринга

[avva]

Недавно в почтенном возрасте 94 лет умер ученый Юрис Хартманис, один из основателей теории сложности в современной информатике. Должен признаться, что я не знал о его существовании. Главное, за что его почитали, как я узнал например из этой заметки - это за статью 1965 года, в которой он с соавтором ввел понятие сложности алгоритма, зафиксированное

Comments

[papa_lyosha]

> "А ведь могло сложиться все по-другому, например, стали бы измерять сложность через число β-редукций в вычислении лямбда-выражения, или что-то типа того..."

А какая по большому счету разница? На определение P и NP это не повлияло бы. Если же считать сложность более точно, то машиной Тьюринга никто не пользуется. Я, например, очень сомневаюсь, что на машине Тьюринга можно отсортировать массив на O(n log n) операций.

[ext_3948950]

Кстати, да, O(n log n) предполагает, что доступ к элементу массива делается за O(1). А на машине Тьюринга это ни в коем случае не так.

[66george]

Только что умер Saul Kripke, который придумал модели Крипке. И всего 81 год, хотя модели он придумал в конце 50-х. Он их в 19 лет придумал, а потом всю жизнь с чистою душою отдыхал (писал книги по философии Витгенштейна).

[gdt]

В вычислительной математике в статьях (по крайней мере) начала 60-х оценивали арифметическую сложность алгоритмов: не просто "быстрый/медленный", а что-нибудь типа O(NlogN). Плохо представляется, что могло быть как-то иначе.

[livelight]

Оценки вида O(NlogN) хороши только при уточнении, какого рода операции считают. Даже чисто цифродробительные алгоритмы могли измерять, например, так: столько-то операций сложения и столько-то - умножения, потому что умножать тогда было намного больнее. А то ж алгоритм со сложностью O(NlogN) операций взлома приватного ключа RSA 4096 может оказаться в большинстве случаев плох по сравнению с алгоритмом, имеющим сложность O(N^2) операций сложения 64-битных целых чисел.

[gdt]

Да, конечно, считали число умножений.

[yyi]

Тот же Хартанис пишет как в знаменито письме Геделя к фон Нейману он считает время как шаги ТМ. так что что-то тут не так.

[livelight]

Я помню, как нам на лекции рассказали, что эта самая полиномиальная или какая-то другая сложность измеряется относительно длины записи входных данных. Учитывая, что длина записи чисел растёт с ростом самих записываемых чисел логарифмически (хотя и линейно относительно количества записанных разных чисел), это было на тот момент для меня совершенно не очевидно.