2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу Пред.  1, 2
 
 Re: Неконструктивная сложность алгоритма
Сообщение06.06.2024, 15:37 
mihaild
В инете про алгоритм Левина почти ничего. Где почитать?

 
 
 
 Re: Неконструктивная сложность алгоритма
Сообщение09.06.2024, 13:51 
Евгений Машеров в сообщении #1641485 писал(а):
Мне кажется, что если доказать отсутствие алгоритма меньшей сложности можно даже без предъявления алгоритма, то наличие "быстрого алгоритма" предполагает явное описание алгоритма. Без этого можно только высказывать гипотезу о его существовании.

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

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

 
 
 [ Сообщений: 18 ]  На страницу Пред.  1, 2


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group