Меняется ли сложность сильно NP-трудных или неполных задач, когда их входные данные унарно кодируются?

12

Меняется ли сложность задачи с полной NP-сложностью или NP-полной (как, например, определено здесь ), когда ее вход является унарным, а не двоичным?

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

Является ли понятие сильно ...- сложным и для других классов сложности, например, более высоких классов полиномиальной иерархии времени?

Ранее я задавал этот вопрос на stackoverflow.com, но было отмечено, что он более уместен здесь.

user2145167
источник
Должен ли я лучше задать этот вопрос на cstheory.stackexchange.com ? Я просто не знал, что это существует. Ответы здесь не идут в направлении, на которое я надеялся.
user2145167
Почему они не? Они (насколько я могу судить) правильны, так что, возможно, ваш вопрос не тот, который вы хотите задать? Кроме того, « Теоретическая информатика» предназначена для вопросов TCS исследовательского уровня , а этот вопрос, безусловно, не таков.
Рафаэль

Ответы:

4

Проблема размера закодированного в унарном формате, - это размер и если двоичный файл. Если требуется время , это в первом случае и во втором случае. Таким образом, алгоритм, который является полиномиальным для первого случая, вероятно, будет экспоненциальным для второго. Кодирование задачи может радикально изменить сложность алгоритма.N log N F ( N ) F ( размер ) F ( 2 размера )NNlogNF(N)F(size)F(2size)

vonbrand
источник
3

Нет.

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

JeffE
источник
2
Я думаю, что вопрос в том, является ли у любой NP-трудной задачи унарная версия не NP-трудной. П 1PP1
Рафаэль
2

Короткий ответ: если вход имеет одинарное кодирование, то он длиннее . Это экспоненциально длиннее. Теперь алгоритм, который работает за полиномиальное время по размеру входных данных, имеет «достаточно времени» для решения проблемы, просто потому, что сам вход экспоненциально длиннее, чем в исходной задаче.

Ран Г.
источник
1

Если посмотреть на проблему формулировки, указанную в ответе Джеффа, то ответ - да.

Рассмотрим проблему с ранцем . У него есть псевдополиномиальный алгоритм, то есть тот, в котором среда выполнения ограничена полиномом из числа, закодированного во входных данных. Поскольку в унарном кодировании значения соответствуют длине, это алгоритм за полиномиальное время для унарной версии.

Фактически, каждая слабо NP-полная задача попадает в эту категорию.

Рафаэль
источник
Побочный вопрос, но я так и не понял - как ты вообще что-то «кодируешь» в унарном? Разве вам не нужен какой-то разделитель?
user541686
@ Mehrdad Да, и нет. Да; разделительные символы обычно не учитываются в этом смысле, ср. также ввод против алфавита ленты; здесь мы рассматриваем только размер входного алфавита. Нет; В принципе, для кодирования кортежей и счетных наборов чисел достаточно одного числа, поэтому вам не нужны символы разделения. Это явно не полезно для «работы» с такими машинами, но оправдывает игнорирование разделительных (и других управляющих) символов.
Рафаэль
Хм ... я не уверен, что понимаю твою часть "нет"; как бы вы узнали, где заканчивается число, если в конце не было разделителя? Мне это кажется чем-то вроде круговой логики: если мы игнорируем разделители, то фактически возникает вопрос: «если мы заставим вход занимать экспоненциально больше места, изменит ли это время выполнения экспоненциального алгоритма относительно размера ввода? ?» чей ответ тривиально да ... по определению. Это не столько изменяет кодировку, сколько искусственно добавляет избыточные биты, если учесть разделители.
user541686
@ Mehrdad Хорошо, я думал только о том, чтобы отделить несколько чисел друг от друга. В любом случае вам нужны маркеры конца, соответственно. «пустые» символы на машинах Тьюринга; от которого ты не сможешь избавиться. Остальное вы можете закодировать в одно число (очевидно, при штрафных санкциях во время выполнения).
Рафаэль