Почему полиномиальное время называется “эффективным”?

Question

Почему в информатике любая сложность, составляющая не более полинома, считается эффективной?

Для любого практического применения^(а), алгоритмы со сложностью $ n ^ {\ log n} $ выполняются намного быстрее, чем алгоритмы, которые выполняются во времени, скажем, $ n ^ {80} $, но первый считается неэффективным, в то время как второй эффективен.Где тут логика?!

^{(a) Предположим, например, что число атомов во Вселенной составляет приблизительно $ 10 ^ {80} $.}

Answer 1

Другая перспектива «эффективности» заключается в том, что полиномиальное время позволяет нам определить понятие «эффективности», которое не зависит от машинных моделей. В частности, существует вариант диссертации церкви-коричке, который называется «Эффективный тезис о церковном котле», в котором говорится, что любая проблема, которая запускается в полиномиальное время на видной модели машины, также будет работать в полиномиальном времени на другой одинаково мощной машине.

Это более слабое утверждение для общего тезиса КТ, и является «своего рода» нарушением как рандомизированными алгоритмами, так и квантовыми алгоритмами, но не подвергается нарушению в смысле способности решить проблему NP в поли-времени, изменяясь Модель машины.

В конечном итоге это причина, по которой многочленное время является популярным понятием в теориях. Однако большинство людей понимают, что это не отражает «практическую эффективность». Подробнее об этом, пост Дика Липтона о 'Галактические алгоритмы'Это отличное чтение.

Answer 2

Теоретически, мы заботимся о асимптотическом поведении и описываем классы проблем и алгоритмов, основанных на их асимптотическом поведении. Ключевое слово здесь асимптотический. Анкет $ O (n^{80}) $ быстрее, чем $ o (n^{ log n}) $ асимптотически, т. Е. Начиная с $ n> 1208925819614629174706176 $ (который, кстати, называется: септиллион!), Предполагая единицу подразделения. Постоянные коэффициенты, и нет условий низкого порядка.

На практике, однако, внимание уделяется как показателям, так и постоянным коэффициентам. В практике размеры ввода не могут расти до септиллионов, поэтому, да, $ n^{ log n} $ для всех целей будет превосходным выбором $ n^{80} $. Другие факторы также имеют значение в практике: параллелизм, паттерны доступа к памяти (например, местность).

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

Другой пример, самый быстрый алгоритм умножения матрицы, известный Алгоритм Coppersmith-Winograd который работает в $ o (n^{2,3737}) $ (есть недавние улучшения; больше здесь) Тем не менее, это никогда не было реализовано, потому что (1) трудно (2) постоянный коэффициент является гигантским. Все линейные пакеты алгебры используют менее оптимальные Страссен.

TL; DR Теория заботится о асимптотическом поведении, чтобы сравнить алгоритмы, поскольку предел входного размера достигает произвольно больших чисел.

Answer 3

В этом ответе будет рассмотрена "общая картина" контекста вашего вопроса.Информатика на самом деле является относительно молодой и в некоторой степени открытой наукой, и у нее пока нет хороших ответов на некоторые базовые вопросы.Основной вопрос "что эффективно вычисляется" - это либо точно или грубо говоря формализованный в CS (в зависимости от мнения) как известная проблема P vs NP (или тесно связанная проблема P vs Exptime), и его все еще Открыть после более чем четырех десятилетий первоначального появления Cook / Levin ~ 1970 и интенсивной работы величайших в мире компьютерщиков (и многие математики также заинтересованы в этой проблеме как фундаментальной).

Таким образом, другими словами, даже с Грубо определение "эффективного" как P времени и одна из самых ценных научных наград, а именно премия в размере 1 млн долларов, присуждаемая задаче более 10 лет, — информатика не может даже доказать, что некоторые задачи (близкие к этой границе) должны иметь или не иметь эффективные алгоритмы (Ptime).Поэтому точное определение "эффективного", более точное, чем время P, не требуется или даже возможный в это время.Если / когда гипотеза P vs NP будет разрешена тем или иным способом, возможно или предположительно будет возможно более строгое определение термина "эффективный".

Более того, кому-то может показаться, что определение Ptime термина "эффективный" может быть даже немного "неаккуратным", и большинство компьютерщиков, вероятно, согласятся, и почти все они считают, что гипотеза P vs NP имеет первостепенное значение для решения, вплоть до того, что они могут даже считать это утверждение или наблюдение тривиальными....другими словами, так сказать, это незавершенная работа / мы работаем над этим.(фактически, ведущие специалисты по информатике даже заходят так далеко, только наполовину в шутку, чтобы регулярно ссылаться на разрыв и отсутствие прогресса / окончательного разделения как смущающий.)

На самом деле существует даже тесно связанный/значительно сильнее гипотеза, отличная от P против NP, а именно NP против P / poly, которая также не может быть решена с помощью информатики в настоящее время.это предполагает, что задачи NP-времени не могут быть решены с помощью Любой Схемы "P-размера", т.е. даже не ограничены теми схемами, которые могут быть созданы алгоритмами / машинами Тьюринга.

Что касается того, насколько сложным может быть P против NP — есть веские основания думать, что это может быть по крайней мере, так же сильно как очень старая гипотеза Римана в математике (сейчас 1.5 столетие старый), потому что оба уже более десяти лет получают одну и ту же награду в размере 1 млн долларов, и ни один из них еще не был раскрыт первым.

Итак, другими словами, точное определение того, какие алгоритмы действительно "эффективны", на самом деле является одним из наиболее важные и трудные из существующих открытых задач в теоретической науке и математике.

На самом деле вопрос о том, "что эффективно вычисляется", на самом деле еще более тонкий, потому что существует вариант тезиса Черча-Тьюринга, называемый тезисом CT в P-time, и неизвестно, действительно ли квантовые вычисления нарушает IT.Благодаря прорывному результату Шора в области QM в режиме P-time факторинг задумался о кардинальном повороте в этом исследовании.Другими словами, проблема того, что эффективно вычисляется, на самом деле правдоподобно сводится к принципам глубокой физики и касается того, могут ли квантовые вычисления вычисляться более эффективно, чем классические вычисления, что также является широко открытой проблемой в теоретической CS и продвинутой физике.

Таким образом, можно даже добавить, что P vs NP и вопрос эффективных вычислений могут иметь решающее или фундаментальное значение в дополнение к CS и математике — физика.

[1] Проблема P vs NP, википедия

[2] Проблемы с премией тысячелетия

[3] Класс P/Poly, википедия

[4] Алгоритм Шора

Answer 4

Алгоритмы полинома времени считаются эффективными только по сравнению с самым сложным не полиномиальным временем, особенно так называемым NP-полным. Смотрите изображение: Диаграмма Euler для P, NP, NP-Complete и NP-Hard.