Почему бы не взять одинарное представление чисел в числовых алгоритмах?

15

Алгоритм псевдополиномиального времени - это алгоритм, который имеет полиномиальное время работы на входном значении (величина), но экспоненциальное время работы на входном размере (количество бит).

Например, для проверки, является ли число простым или нет, требуется выполнить цикл по числам от 2 до n - 1 и проверить, является ли n mod i нулевым или нет. Если мод занимает O (1) времени, общая сложность времени будет O (n).nn1n i

Но если мы позволим быть числом необходимых битов для записи входных данных, то x = log n (двоичный), поэтому n = 2 x, и время выполнения задачи будет O ( 2 x ), что является экспоненциальным.xx=lognn=2x2x

Мой вопрос заключается в том, что если мы рассмотрим унарное представление входного , то всегда x = n и тогда псевдополиномиальное время будет равно сложности полиномиального времени. Так почему же мы никогда этого не делаем?nx=n

Более того, поскольку для рюкзака существует алгоритм псевдополиномиального времени, при взятии рюкзак будет полиномиальным в результате P = NPx=n

М ама Д
источник
3
На самом деле, мы делаем это, но не часто. По тем же причинам мы обычно не имеем дело с унарными языками, но есть много интересных результатов, связанных с этими животными. Вы смотрели на это?
Андре Соуза Лемос
2
Да, если вы уберете разницу между размером и величиной, вы потеряете все концепции, основанные на этой разнице.
Андре Соуза Лемос
7
Потому что это одевает демона в красивое платье. Он не делает ничего быстрее, он только делает бессмысленным «сложность времени выполнения».
Рафаэль
4
@Drupalist На самом деле неизвестно, что унарная задача о ранце является NP-полной, поскольку нормальное сведение к задаче о ранце предполагает, что числа записываются в двоичном виде. Если вы попытаетесь выполнить стандартное сокращение, но запишите числа в унарном виде, сокращение не может быть вычислено за полиномиальное время. В результате, проблема унарного ранца, разрешимая за полиномиальное время, не означает, что P = NP.
templatetypedef
2
Вы можете проверить другие ответы, помеченные псевдополиномом , в частности, этот .
Рафаэль

Ответы:

17

Это означает, что унарный рюкзак находится в P. Это не означает, что рюкзак (с двоичными числами) находится в P.

Рюкзак, как известно, NP-полный. Если бы вы показали, что рюкзак находится в P, это показало бы, что P = NP.

Но вы не показали, что рюкзак находится в P. Вы показали, что унарный рюкзак находится в P. Однако, как известно, унарный рюкзак не является NP-полным (действительно, стандартное подозрение заключается в том, что он, скорее всего, не является NP-полным). ). Следовательно, помещение одинарного ранца в P не означает, что P = NP.


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


Чтобы ответить на следующий вопрос об алгоритме динамического программирования для задачи о ранце:

Да, один и тот же алгоритм динамического программирования может применяться как к рюкзакам, так и к одинарным рюкзакам. Время его выполнения является полиномиальным по величине чисел, но экспоненциальным (не полиномиальным) по длине чисел при кодировании в двоичном виде. Таким образом, его время работы является полиномиальным по длине входа, когда вход кодируется в унарном виде, но не является полиномиальным по длине входа, когда вход кодируется в двоичном формате. Вот почему мы действительно рассмотреть этот алгоритм динамического программирования быть полиномиальным алгоритмом для одноместный рюкзаке, но не считаем , что это полиномиальный алгоритм (бинарной кодировкой) ранец.

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

DW
источник
1
Большое спасибо, я не знал, что класс сложности унарных и неунарных одинаковых алгоритмов может быть разным. Почему решение динамического программирования стандартного ранца не может быть применено к одинарному ранцу, и это привело к другому классу сложности? У меня проблемы с пониманием унарной версии проблем.
М А Д Д
@Drupalist, я отредактировал свой ответ, добавив два абзаца в конце, чтобы ответить на этот вопрос.
DW
Большое спасибо, из того, что я понимаю, разница между размером ввода и его величиной является причиной различия между полиномом и псевдополиномом, используя унарное представление, я попытался устранить эту разницу, если мы забудем рюкзак и вернемся к числовому алгоритмы, я хотел бы знать, установив что будет интерпретация полинома и псевдополинома? Еще раз спасибоx=n
M Ama D
@Drupalist, я не совсем уверен, что вы подразумеваете под установкой , поэтому я не уверен, что ответить. В этот момент я хотел бы предложить, чтобы было лучше задать новый (самостоятельный) вопрос (и определить все ваши переменные в этом вопросе). Эта платформа не так хороша для последующих вопросов или задних вопросов: лучший способ справиться с ней - задать новый вопрос, основываясь на том, что вы узнали из ответов на этот вопрос. x=n
DW
1
@NikosM. Хорошо, понял. Спасибо за ответ. Лично я не верю, что это утверждение неверно, поэтому я собираюсь оставить все как есть. (Мое рассуждение: длина входных данных зависит от выбора представления, поэтому я не думаю, что это противоречит всему, что вы написали.) Однако вполне возможно, что моя точка зрения может быть слишком узкой, или что более подробное объяснение или объяснение из другая точка зрения может добавить ценность. Не стесняйтесь написать дополнительный ответ или предложить редактирование, если считаете, что этот момент может быть более понятным.
DW
6

Я бы добавил одну маленькую вещь к ответу DW:

Я видел людей, которые думают, что поскольку унарный рюкзак находится в P, мы можем использовать его вместо рюкзака, у которого лучшие современные алгоритмы имеют экспоненциальное время.

Пусть входом будет и k и рассмотрим алгоритм динамического программирования для рюкзака и унарного рюкзака. Время работы для них обоих O ( n k ) . Это то же самое время выполнения. Т.е., если у вас есть вход, не имеет значения, используете ли вы динамическое программирование для унарного рюкзака или динамическое программирование для рюкзака. Им обоим потребуется (примерно) одинаковое количество времени для решения проблемы. Теоретически, где бы вы ни использовали одно, вы можете использовать и другое. Вам просто нужно преобразовать числа из одинарных в двоичные и наоборот.W={w1,,wn}kO(nk)

Так какой смысл определять сложность алгоритмов в зависимости от размера входных данных? Почему бы не всегда указывать их в терминах параметров как ?O(nk)

Если вы заботитесь о проблеме в изоляции, вы можете сделать это. На самом деле это то, что люди в алгоритмах часто делают. Сложность алгоритмов графа часто выражается через число вершин и количество ребер, а не размер строки, которая их кодирует.

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

k100100k21001kk21001

nnp(n)kp(n)k2p(n)1kk

nk

Кава
источник
Большое спасибо, еще один вопрос, путем преобразования входных данных в их унарное представление, что произойдет с проблемой определения, является ли число простым или нет? Эта проблема является полиномиальной, основанной на входной амплитуде, но экспоненциальной, основанной на входных битах (как я указал в вопросе), улучшит ли это преобразование что-нибудь лучше?
М ам Д
NО(N)Nбзнак равно21024-121024-121024-1
Каве
Хорошее уточнение, однако взгляните на мой комментарий под ответом DW, который связан с этим постом
Никос М.
2

Короче говоря, я покажу вам, почему.

Предположим, у вас есть алгоритм факторизации. За исключением небольшой разницы, что один принимает целые числа для ввода, а другойTaLLY, Как видите, оба фрагмента кода похожи.

x = input integer

factors = [];

for i in range(1, x + 1):
    if x % i == 0:
     factors.append(i)

 print(factors)

Обратите внимание, что приведенный выше алгоритм является полиномом числового значения Икс, Это займетИксколичество шагов в цикле. Но когда дело доходит до размера бит на самом делеО(2N),

Предположим, я делаю небольшое редактирование кода, который будет принимать TaLLY/UNaрY, Теперь будетО(N) время в значении и длине ввода Икс,

x = input tallies

factors = [];

for i in range(1, x + 1):
    if x % i == 0:
     factors.append(i)

 print(factors)

Входное представление не заставляет код работать быстрее. Несмотря на то, что 2-й алгоритм действительно много времени. Это не очень практично в поиске факторов для RSA.

Трэвис Уэллс
источник
Хороший пример, спасибо
M