Неконструктивная сложность алгоритма

[John Maller]

mihaild
В инете про алгоритм Левина почти ничего. Где почитать?

[Malyar]

Евгений Машеров в сообщении #1641485 писал(а):

Мне кажется, что если доказать отсутствие алгоритма меньшей сложности можно даже без предъявления алгоритма, то наличие "быстрого алгоритма" предполагает явное описание алгоритма. Без этого можно только высказывать гипотезу о его существовании.

В других областях математики царит неконструктивщина. Почему ж теория алгоритмов исключение? Не берутся за работу в этой области что ли настоящие математики: только программисты, ориентированные исключительно на практику?

[dgwuqtj]

Может, просто ещё не придумали хорошую качественную теорию. А работающих "чистых" математиков там хватает. Придумали же, например, понятие алгебраической сложности. Чем-то ситуация напоминает аддитивную теорию чисел и теорию трансцендентных чисел.