что такое полиномиальное время
Определения алгоритма, работающего за полиномиальное время и сильно полиномиальное время
Википедия определяет это как
Считается, что алгоритм имеет полиномиальное время, если его время выполнения ограничено сверху полиномиальным выражением в размере входных данных для алгоритма, т. Е. для некоторой константы k. T ( n ) = O ( n k ) ‘ role=»presentation»> T ( N ) знак равно О ( N К )
Алгоритм работает за сильно полиномиальное время, если [8]
количество операций в арифметической модели вычислений ограничено полиномом от числа целых чисел во входном экземпляре; и
пространство, используемое алгоритмом, ограничено полиномом по размеру входных данных.
Говорят, что алгоритм с рациональным вводом работает за полиномиальное время, если
Говорят, что алгоритм с произвольным вводом работает за строго полиномиальное время, если
Пожалуйста, поправьте меня, если я ошибаюсь. Ниже приведены буквальные различия, которые я заметил:
Для сильно полиномиальных алгоритмов времени определение Корта и Вигена и определение Википедии требуют полиномиального времени в объеме входной памяти. Но для K и V дополнительно требуется полиномиальное время в количестве чисел в любом входе, в то время как в Википедии дополнительно требуется полиномиальное пространство для хранения во входном размере.
Значит, определения K и V и Wikipedia для этих двух понятий эквивалентны соответственно? Какие еще различия и отношения между ними?
Спасибо и всего наилучшего!
Прежде чем приступить к формальным определениям, рассмотрим, что стремится отличить «сильно / слабо» классификация.
O ( 1 ) ‘ role=»presentation»> О ( 1 )
Набор алгоритмов, которые выполняются по числу арифметических операций, полиномиальных по числу входных чисел, хорошо определен, но перекрывается с классом алгоритмов, которые принимают экспоненциальное число шагов TM по длине двоично-кодированного ввода (см. Примеры ). Следовательно, для этого набора свойства во втором абзаце не будут сохраняться. Чтобы исключить нежелательное пересечение, мы добавляем условие для полиномиального пространства TM [*].
В [1] это указано двумя способами:
O ( n 3 ) ‘ role=»presentation»> О ( N 3 ) O ( n 2 ) ‘ role=»presentation»> О ( N 2 )
[*] Второе условие везде задается как полиномиальное пространство, тогда как требование полиномиального времени имеет для меня больше смысла. Первый более содержательный, но странный. Существуют ли сильно-полиномиальные алгоритмы, которые занимают больше полиномиального времени? Обратите внимание, что пример повторного возведения в квадрат не занимает ни полиномиального времени, ни полиномиального пространства.
[1] Grötschel, Martin; Ласло Ловаш, Александр Шрайвер (1988). «Сложность, оракулы и численные вычисления». Геометрические алгоритмы и комбинаторная оптимизация. Springer. ISBN 0-387-13624-X.
Почему полиномиальное время называется «эффективным»?
Почему в информатике любая сложность, которая в большинстве случаев является полиномиальной, считается эффективной?
Другая точка зрения на «эффективность» состоит в том, что полиномиальное время позволяет нам определить понятие «эффективность», которое не зависит от моделей машин. В частности, существует вариант тезиса Черча-Тьюринга, который называется «эффективный тезис Черча-Тьюринга», в котором говорится, что любая проблема, которая выполняется за полиномиальное время на типе модели машины, будет также выполняться за полиномиальное время на другой, столь же мощной модели машины.
Это более слабое утверждение к общему тезису КТ, и его «нарушают» как рандомизированными алгоритмами, так и квантовыми алгоритмами, но оно не нарушается в смысле возможности решения NP-трудной задачи за многократное время путем изменения модель машины.
Это, в конечном счете, причина, по которой полиномиальное время является популярным понятием в теории. Однако большинство людей понимают, что это не отражает «практическую эффективность». Более подробно об этом читал пост Дика Липтона « Галактические алгоритмы ».
TL; теория DR заботится об асимптотическом поведении, чтобы сравнивать алгоритмы, поскольку предел входного размера достигает сколь угодно больших чисел.
Этот ответ рассмотрит контекст «большей картины» вашего вопроса. Информатика на самом деле является относительно молодой и несколько открытой наукой, и у нее пока нет хороших или даже хороших ответов на некоторые основные и фундаментальные вопросы. Основной вопрос «что эффективно вычисляется» либо точно или грубо формализован в CS (в зависимости от мнения) как известная проблема P vs NP (или тесно связанная проблема P v Exptime), и он все еще остается открытым после более чем четырех десятилетий Первоначально был представлен Cook / Levin
1970 и интенсивной работой величайших компьютерных ученых мира (и многие математики также интересуются этой проблемой как фундаментальной).
На самом деле существует даже тесно связанная / значительно более сильная гипотеза, чем P против NP, а именно NP против P / poly, которая в настоящее время также не может быть решена компьютерной наукой. это предполагает, что проблемы времени NP не могут быть решены никакими схемами «P-размера», то есть даже не ограничены теми схемами, которые могут быть созданы алгоритмами / машинами Тьюринга.