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

50

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

Для любого практического применения (a) алгоритмы со сложностью работают намного быстрее, чем алгоритмы, выполняющиеся во времени, скажем, , но первый считается неэффективным, а второй - эффективным. Где логика ?! n 80nlognn80

(a) Предположим, например, что число атомов во вселенной составляет приблизительно .1080

Ран Г.
источник
3
Я не уверен, что согласен с вашей предпосылкой. Я думаю, что большинство людей сочли бы довольно неэффективным (хотя, конечно, это также зависит от констант и от решаемой проблемы). n80
sepp2k
16
Я бы посчитал для любого очень неэффективным. У вас есть пример асимптотического анализа, доведенного до необоснованной крайности. Не существует естественных алгоритмов (которые я знаю) с времени выполнения. Однако существуют естественные алгоритмы с времени выполнения для некоторых задач и фундаментальные вопросы теории сложности о том, существует ли полиномиальный алгоритм для таких задач. c > 3 n 80 2 nncc>3n802n
Джо
5
Я думаю, что этот вопрос не должен быть опущен, потому что люди не согласны с предпосылкой (если предположить, что это было причиной). Предполагается, что положительные и отрицательные оценки указывают на качество вопроса, а не на его содержание (если они относятся к теме).
Алекс тен Бринк
8
@RanG. и полная цитата (выделено мной): тезис Кобхэма гласит, что P - это класс вычислительных задач, которые «эффективно разрешимы» или «податливы»; на практике некоторые проблемы, о которых не известно, что они есть в P, имеют практические решения, а некоторые
Джо
6
В литературе (теоретического CS) слово «эффективный» является синонимом «полиномиального». Возможно, это отличается от других (более практичных) подполей.
Ран Г.

Ответы:

32

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

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

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

Суреш
источник
15
Вторая, прагматическая причина выбора P состоит в том, что он замкнут относительно сложения, умножения и возведения в степень с константами. Это удобно при составлении алгоритмов / машин; если строительные блоки эффективны, таков и результат.
Рафаэль
Мне просто любопытно, кто-нибудь знает, используется ли на практике термин "галактический алгоритм"?
Хуан Бермехо Вега
Это не такой старый термин. Но я начал его использовать :)
Suresh
24

Теоретически мы заботимся об асимптотическом поведении и описываем классы задач и алгоритмов на основе их асимптотического поведения. Ключевое слово здесь асимптотическое . быстрее, чем асимптотически, т. Начиная с (который, кстати, называется: septillion!), Принимая единичные постоянные коэффициенты и не низкие УсловияO ( n log n ) n > 1208925819614629174706176O(n80)O(nlogn)n>1208925819614629174706176

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

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

Другим примером, самым быстрым из известных алгоритмов умножения матриц, является алгоритм Копперсмита-Винограда, который работает в (есть недавние улучшения; подробнее здесь ). Тем не менее, он никогда не был реализован, потому что (1) это трудно (2) постоянный коэффициент является гигантским. Все линейные пакеты алгебры используют менее оптимальный Штрассен .O(n2.3737)

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


источник
Они "выбирают подчиненный алгоритм"? Разве вы не имеете в виду «выбрать лучший алгоритм»?
битовая маска
Еще один хороший пример - сортировка вставкой или быстрая сортировка. Сортировка вставок - а быстрая сортировка - . Однако при небольших входах, скажем, 10, сортировка вставок примерно в два раза быстрее, чем быстрая сортировка! Фактически, оптимизированная быстрая сортировка использует сортировку вставкой для небольших массивов. O ( n l g n )Θ(N2)O(nlgn)
Роберт С. Барнс
Почему мы не считаем асимптотически кубические алгоритмы «плохими» и асимптотически квадратичные алгоритмы «хорошими»? Этот ответ напрашивается на вопрос.
Джехлин
2

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

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

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

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

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

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

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

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

[1] P против NP, Википедия

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

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

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

ВЗН
источник
исправление: P против Pspace, а не P против ExpTime
vzn
-2

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

Гильермо А Пуссетто
источник
1
«по сравнению с самым сложным неполиномиальным временем, особенно так называемым NP-Complete» - проблемы NP-Complete, как известно, не являются полиномиальными, и они, безусловно, не самые сложные.
Рафаэль