Есть ли естественная проблема на натуральных объектах, которая является NP-полной?

30

Любое натуральное число может рассматриваться как битовая последовательность, поэтому ввод натурального числа аналогичен вводу последовательности 0-1, поэтому проблемы с NP-заполнением с натуральными входами, очевидно, существуют. Но есть ли естественные проблемы, то есть те, которые не используют некоторую кодировку и специальную интерпретацию цифр? Например, "На прайм?" Это такая естественная проблема, но эта проблема в P. Или "Кто победит в игре Nim с кучами размера 3, 5, n, n?" это еще одна проблема, которую я считаю естественной, но мы также знаем, что это связано с P. Меня также интересуют другие классы сложности, а не NP.

Обновление: Как указал Эмиль Йержабек, учитывая a,b,cN, чтобы определить, имеет ли ax2+byc=0 решение над натуральными, NP-полно. Это именно то, что я имел в виду, как естественный, за исключением того, что здесь ввод три числа вместо одного.

Обновление 2: И после более чем четырехлетнего ожидания Дэн Брамлев дал «лучшее» решение - обратите внимание, что оно все еще не завершено из-за рандомизированного сокращения.

domotorp
источник
1
Мне известна проблема разбиения по NEXP, где входное значение представляет собой целое число n, и задача состоит в том, чтобы определить, существует ли допустимый листинг сетки nxn. Если вам это интересно, я поищу газету.
Робин Котари
2
@Emil: комментарий domotorp был ответом на путаницу, которая у меня была. Но это было недоразумение с моей стороны, поэтому я удалил комментарий. Я думаю, что входные данные должны быть одним натуральным числом, которое не должно ничего кодировать.
Робин Котари
8
@domotorp: NP-полная проблема , которую я имел в виду это, учитывая , Ь , с N , определить , является ли х 2 + б у - с = 0 имеет решение х , у N . Другой вариант, с учетом a , b , c , определить, существует ли x c такой, что . (Результат от dx.doi.org/10.1145/800113.803627 .)a,b,cNax2+byc=0x,yNa,b,cxcx2a(modb)
Эмиль Йержабек поддерживает Монику
3
Почему ответ на этот вопрос явно НЕТ ? У каждой NP-сложной проблемы есть экземпляры, которые «кодируют» логическую схему; возможно, это то, что значит быть NP-hard!
Джефф
2
@domotorp: возможно , еще один хороший «естественный» кандидат является задачей нахождения минимального аддитивных цепочек одного заданного числа : от О количестве минимального Сложения цепи :»... Проблема нахождения минимального сложения цепи для набора из чисел NP-полной. Это не означает , как это иногда утверждают , что найти минимальную аддитивную цепочку для является NP-полной. Однако, можно легко сделать вывод , что задача нахождения всех минимальных аддитивных цепочек для числа является NP-полная ... "nmnn
Марцио Де Биаси

Ответы:

17

Эта проблема имеет вариацию с одним целочисленным вводом:

Имеет ли делитель строго между двумя самыми большими простыми факторами?n

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

Вот еще один вариант той же проблемы, с аналогичным сокращением проблемы разделения:

Является ли произведением двух целых чисел, которые отличаются менее чем на ?nn14

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

Я думаю, что интересно смотреть на эти примеры вместе с теоремой Махани : если и мы можем найти ближайшие простые числа, то эти множества не редки. Приятно получить чисто арифметическое утверждение из теории сложности (хотя это только предположительно и, вероятно, легко доказывается другим способом).PNP

Дан Брумлев
источник
что вы подразумеваете под «если P ≠ NP и мы можем найти ближайшие простые числа»?
T ....
1
@ao., см . ответ Питера Шора, описывающий сокращение. Чтобы она была NP-полной, нам нужно найти простое число с за время . Я постараюсь дать свой собственный отчет обо всем этом здесь позже. p|pn|<naO((logn)k)
Дан Брумлев
Какие наборы не являются плотными?
Т ....
33

Основываясь на обсуждении, я опубликую это как ответ.

Как доказали Мандерс и Адлеман , следующая задача является NP-полной: по заданным натуральным числам определите, существует ли натуральное число такое, что .x c x 2aa,b,cxcx2a(modb)

Проблема может быть эквивалентно сформулирована следующим образом : с учетом , определить , является ли квадратичная имеет решение .x 2 + b y - c = 0 x , y Nb,cNx2+byc=0x,yN

(В оригинальной статье говорится о проблеме с , но нетрудно понять, что ее можно свести к случаю )a = 1ax2+byca=1

Эмиль Йержабек поддерживает Монику
источник
10

Вот проблема с одним натуральным числом в качестве входных данных.NEXP

Проблема состоит в том, чтобы наложить сетку с фиксированным набором плиток и ограничениями на соседние плитки и плитки на границе. Все это является частью спецификации проблемы; это не часть ввода. На входе только число . Проблема в том, что для некоторого выбора правил как показано вn NEXPn×nnNEXP

Д. Готтесман, С. Ирани. Квантовая и классическая сложность трансляционно-инвариантных задач Тайлинга и Гамильтона. Учеб. 50-й ежегодный симп. по основам информатики, 95-104 (2009), DOI: 10.1109 / FOCS.2009.22 . Также arXiv: 0905.2419 .

Проблема определена на стр. 5 версии arxiv.

Кроме того, они также определяют аналогичную проблему, которая является -complete, которая является квантовым аналогом с ограниченной ошибкой . (Классическим ограниченным аналогом ошибки является .) NEXP NEXP MA EXPQMAEXPNEXPNEXPMAEXP

Робин Котари
источник
3
+1, но немного сложно утверждать, что число используется «естественным» образом, поскольку оно кодирует входные данные для конкретной машины Тьюринга (в частности, мозаика существует, если машина Тьюринга принимает , где является в перечислении потенциальных входных строк). Все еще очень интересный результат. х х нnxxn
mjqxxxx
Я максимально согласен с mjqxxxx.
Domotorp
2

Я думаю, что используя один из ограниченных во времени вариантов сложности Колмогорова, вы можете построить задачу, которая использует только двоичное представление числа и (я думаю) вряд ли будет в ; неофициально это разрешимый вариант проблемы « сжимаем?»: нPn

Задача: При заданном существует ли машина Тьюринга такая, что и на пустой ленте выводит менее чем за шага, где - длина двоичного представленияM | М | < l M n l 2 l = log nnnM|M|<lMnl2l=lognn

Это явно в , потому что, учитывая и , просто смоделируйте для шагов и, если он остановится, сравните результат с . н М М л 2 нNPnMMl2n

Марцио де Биаси
источник
Я думаю, что эта проблема основана на ТМ, но, конечно, невозможно провести черту.
Домоторп
Чтобы уточнить комментарии domotorp, я бы сказал, что тот факт, что в описании проблемы вообще нужно использовать понятие машины Тьюринга, исключает ее как «естественную проблему о натуральных числах». (Если мы предположим, что естественная проблема, связанная с натуральными числами, - это проблема, общий формат которой будет согласован, например, с тем, что Ферма изучил ее, не предполагая слишком контрфактуальной истории математики.)
Ниль де Бёдрап,
2

Наша статья FOCS'17 по короткой арифметике Presburger является примером «естественной» проблемы, которая является NP-c, и использует постоянное число целых чисел во входных данных, скажем, . Он отличается от Мандерса-Адлемана тем, что все ограничения являются неравенствами. Посмотрите сообщение в блоге Гила Калаи для некоторого фона. CC<220

Игорь Пак
источник
Я думаю, что это более естественно, чем Мандерс-Адлеман. Возможен ли менее переменных и примеров неравенства? 10510
T ....
Нет, 5 переменных самая маленькая. 10 - не уверен. Но на самом деле не может быть меньше 6 ...
Игорь Пак
Есть ли причина и ? Я имею в виду , что доказано , что все и конечное число неравенств в (Точно так же все переменные и неравенство рецептуры есть в ?)? 6 4 P 5 5 P564P55P
T ....
Да. Для меньшего количества переменных проблема в П.
Игорь Пак
2
Да. Это все в нашей статье и диссертации Дэнни Нгуена. math.ucla.edu/~pak/papers/Nguyen-thesis.pdf
Игорь Пак
1

Как насчет проблемы PARTITION ?

Кевин А. Вортман
источник
3
Нет, так как ввод не число, а набор.
Domotorp
1
Так вы спрашиваете о проблемах, для которых экземпляр является ровно одним натуральным числом? Я не думаю, что это ясно в вашем вопросе, так как вы спрашиваете о «проблемах с естественными ресурсами», а ваш пример игры Nim включает в себя четыре числа.
Кевин А. Вортман
Прошу прощения, если я был неопределенным в постановке вопроса.
domotorp