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

30

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

Обновление: Как указал Эмиль Йержабек, учитывая $a,b,c\in \mathbb N,$ чтобы определить, имеет ли $ax^2+by-c=0$ решение над натуральными, NP-полно. Это именно то, что я имел в виду, как естественный, за исключением того, что здесь ввод три числа вместо одного.

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

cc.complexity-theory np-hardness nt.number-theory combinatorial-game-theory domotorp
источник

1

Мне известна проблема разбиения по NEXP, где входное значение представляет собой целое число n, и задача состоит в том, чтобы определить, существует ли допустимый листинг сетки nxn. Если вам это интересно, я поищу газету.

Робин Котари

2

@Emil: комментарий domotorp был ответом на путаницу, которая у меня была. Но это было недоразумение с моей стороны, поэтому я удалил комментарий. Я думаю, что входные данные должны быть одним натуральным числом, которое не должно ничего кодировать.

Робин Котари

8

@domotorp: NP-полная проблема , которую я имел в виду это, учитывая

, определить , является ли

имеет решение

. Другой вариант, с учетом

, определить, существует ли

такой, что . (Результат от dx.doi.org/10.1145/800113.803627 .)

a, b, c \in N

$a,b,c\in\mathbb N$

a x^{2} + b y - c = 0

$ax^2+by-c=0$

x, y \in N

$x,y\in\mathbb N$

a, b, c

$a,b,c$

x \leq c

$x\le c$

x^{2} \equiv a (\mod b)

$x^2\equiv a\pmod b$

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

3

Почему ответ на этот вопрос явно НЕТ ? У каждой NP-сложной проблемы есть экземпляры, которые «кодируют» логическую схему; возможно, это то, что значит быть NP-hard!

Джефф

2

@domotorp: возможно , еще один хороший «естественный» кандидат является задачей нахождения минимального аддитивных цепочек одного заданного числа : от О количестве минимального Сложения цепи :»... Проблема нахождения минимального сложения цепи для набора из чисел NP-полной. Это не означает , как это иногда утверждают , что найти минимальную аддитивную цепочку для является NP-полной. Однако, можно легко сделать вывод , что задача нахождения всех минимальных аддитивных цепочек для числа является NP-полная ... "

n

$n$

m

$m$

n

$n$

n

$n$

Марцио Де Биаси

17

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

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

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

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

Является ли произведением двух целых чисел, которые отличаются менее чем на ? $n$ $n^{\frac{1}{4}}$

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

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

Дан Брумлев
источник

что вы подразумеваете под «если P ≠ NP и мы можем найти ближайшие простые числа»?

T ....

1

@ao., см . ответ Питера Шора, описывающий сокращение. Чтобы она была NP-полной, нам нужно найти простое число с за время . Я постараюсь дать свой собственный отчет обо всем этом здесь позже.

p

$p$

| p - n | < n^{a}

$\vert p - n \vert \lt n^a$

O ((\log n)^{k})

$O((\log{n})^k)$

Дан Брумлев

Какие наборы не являются плотными?

Т ....

33

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

Как доказали Мандерс и Адлеман , следующая задача является NP-полной: по заданным натуральным числам определите, существует ли натуральное число такое, что . $a,b,c$ $x\le c$ $x^2\equiv a\pmod b$

Проблема может быть эквивалентно сформулирована следующим образом : с учетом , определить , является ли квадратичная имеет решение . $b,c\in\mathbb N$ $x^2+by-c=0$ $x,y\in\mathbb N$

(В оригинальной статье говорится о проблеме с , но нетрудно понять, что ее можно свести к случаю ) $ax^2+by-c$ $a=1$

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

10

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

Проблема состоит в том, чтобы наложить сетку с фиксированным набором плиток и ограничениями на соседние плитки и плитки на границе. Все это является частью спецификации проблемы; это не часть ввода. На входе только число . Проблема в том, что для некоторого выбора правил как показано в $n \times n$ $n$ $\text{NEXP}$

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

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

Кроме того, они также определяют аналогичную проблему, которая является -complete, которая является квантовым аналогом с ограниченной ошибкой . (Классическим ограниченным аналогом ошибки является .) $\text{QMA}_\text{EXP}$ $\text{NEXP}$ $\text{NEXP}$ $\text{MA}_\text{EXP}$

Робин Котари
источник

3

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

n

$n$

x

$x$

x

$x$

n

$n$

mjqxxxx

Я максимально согласен с mjqxxxx.

Domotorp

2

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

Задача: При заданном существует ли машина Тьюринга такая, что и на пустой ленте выводит менее чем за шага, где - длина двоичного представления $n$ $M$ $|M| < l$ $M$ $n$ $l^2$ $l = \lceil \log{n} \rceil$ $n$

Это явно в , потому что, учитывая и , просто смоделируйте для шагов и, если он остановится, сравните результат с . $\mathsf{NP}$ $n$ $M$ $M$ $l^2$ $n$

Марцио де Биаси
источник

Я думаю, что эта проблема основана на ТМ, но, конечно, невозможно провести черту.

Домоторп

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

Ниль де Бёдрап,

2

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

Игорь Пак
источник

Я думаю, что это более естественно, чем Мандерс-Адлеман. Возможен ли менее переменных и примеров неравенства?

5

$5$

10

$10$

T ....

Нет, 5 переменных самая маленькая. 10 - не уверен. Но на самом деле не может быть меньше 6 ...

Игорь Пак

Есть ли причина и ? Я имею в виду , что доказано , что все и конечное число неравенств в (Точно так же все переменные и неравенство рецептуры есть в ?)?

\geq 5

$\geq5$

\geq 6

$\geq6$

\leq 4

$\leq4$

P

$P$

\leq 5

$\leq5$

\leq 5

$\leq5$

P

$P$

T ....

Да. Для меньшего количества переменных проблема в П.

Игорь Пак

2

Да. Это все в нашей статье и диссертации Дэнни Нгуена. math.ucla.edu/~pak/papers/Nguyen-thesis.pdf

Игорь Пак

1

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

Кевин А. Вортман
источник

3

Нет, так как ввод не число, а набор.

Domotorp

1

Так вы спрашиваете о проблемах, для которых экземпляр является ровно одним натуральным числом? Я не думаю, что это ясно в вашем вопросе, так как вы спрашиваете о «проблемах с естественными ресурсами», а ваш пример игры Nim включает в себя четыре числа.

Кевин А. Вортман

Прошу прощения, если я был неопределенным в постановке вопроса.

domotorp

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

Ответы: