Проблемы между P и NPC

128

Факторинг и изоморфизм графов - это проблемы в NP, которые, как известно, не находятся в P и не являются NP-полными. Каковы некоторые другие (достаточно разные) естественные проблемы, которые разделяют это свойство? Искусственные примеры, полученные непосредственно из доказательства теоремы Ладнера, не учитываются.

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

Лев Рейзин
источник
Здесь задан похожий вопрос, который может быть полезен: cstheory.stackexchange.com/questions/52/…
Даниэль Апон
1
Связанный вопрос в МО, с несколькими указателями специально для проблем в NP и co-NP, но неизвестно, чтобы они были в P: mathoverflow.net/questions/31821/…
Саламон
1
Существует несколько классов сложности между P и NP-complete, которые в настоящее время рассматриваются как интересные: PPAD, задачи, которые эквивалентны UGC, NP co-NP, BPP, .... Если вы запрашиваете большой список, может Вы делаете это вики-сообществом, пожалуйста?
Андрас Саламон
Спасибо. Я в курсе теоремы Ладнера. Я думаю, что я просил "естественные проблемы". Я думаю, что у PPAD есть Nash Equilibria, так что это имеет значение ...
Лев Рейзин

Ответы:

105

Вот коллекция некоторых ответов проблем между P и NPC:

Лев Рейзин
источник
5
Да, эта процедура работает, как и «официальный» ответ.
Суреш Венкат
12
Было бы здорово добавить ответ в свой список наблюдения. Это определенно будет на моем.
Андрас Саламон
9
Я удаляю Planar MAX 2-SAT из списка, он был показан как NP-полный Guibas et al. в разделе «Аппроксимация многоугольников и подразделений с минимальными путями ссылки» ( springerlink.com/content/y234m35416w043v1 )
Боб Фрейзер,
7
Являются ли какие-либо из этих примеров доказуемо NP-промежуточными, предполагая лишь некоторую «разумную» гипотезу (т. Е. Гипотезу менее тривиальную, чем «эта проблема является NP-промежуточной»)? Если это так, было бы интересно упомянуть, что в этом списке.
Тимоти Чоу
3
@Timothy Chow: Приведенный выше пример, предполагая, что является доказуемо промежуточным, то есть, предполагая, что , дополненная версия проблемы , очевидно, не является ни неполной по Махани, ни по , поскольку это противоречит . N E X P E X P N E X P N P P N E X P E X PNEXPEXPNEXPEXPNEXPNPPNEXPEXP
Джошуа Грохов
45

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

Дэвид Эппштейн
источник
1
Это аккуратная проблема: я не понимал, что это было в подвешенном состоянии.
Суреш Венкат
3
Да, я тоже об этом не знал! Для всех этих проблем / ответов, мне интересно, находятся ли они в подвешенном состоянии, потому что мы думаем, что они действительно или они больше похожи на ПРЕМЬЕРЫ ...
Лев Рейзин
Эта проблема и ее потенциально промежуточный статус должны быть более известными. Можете ли вы дать ссылку на это? Кроме того, есть ли результат, указывающий на то, что он не является NP-полным, как это имеет место для изоморфизма графов и связанных с ним проблем?
Джошуа Грохов
8
Очень симпатичный и важный, но более старый справочник - Терстон, Слеатор и Тарьян, «Расстояние вращения, триангуляции и гиперболическая геометрия», STOC'86 и JAMS'88. Для недавней ссылки, в которой явно упоминается сложность проблемы, которая все еще остается открытой, см. Lucas, «Улучшенный размер ядра для расстояния вращения в двоичных деревьях», IPL 2010, dx.doi.org/10.1016/j.ipl.2010.04. 022
Дэвид Эппштейн
1
Интересно. Исследование пространства вращения также является активной областью исследований. «График вращения k-арных деревьев является гамильтоновым», IPL 2008, dx.doi.org/10.1016/j.ipl.2008.09.013
Чад Brewbaker
38

Проблема, которая не упоминается ни в этом списке, ни в списке МО, является проблемой магистрали. Учитывая мультимножество n (n-1) / 2 чисел, каждое число, представляющее расстояние между двумя точками на линии, реконструирует положения исходных точек.

Обратите внимание, что нетривиальным является то, что для заданного числа d в ​​мультимножестве вы не знаете, какая пара точек находится на расстоянии d единиц.

Хотя известно, что для любого данного случая существует только полиномиальное число решений, неизвестно, как его найти!

Суреш Венкат
источник
Спасибо - это хорошо! Напоминает мне о некоторых других проблемах "локализации". Это на самом деле считается не в р?
Лев Рейзин
Я не знаю, что шлагбаум напрямую связан с известными проблемами сложности. Однако существует факторинг, связанный с «неправильным направлением», в котором проблема шлагбаума может быть сформулирована как проблема факторинга на правильно выбранном полиноме.
Суреш Венкат
1
Известны ли маловероятные последствия этой проблемы, являющейся NP-полной, как для изоморфизма графов (коллапс PH)?
Джошуа Грохов
не то, чтобы я знал. это так мало изучено, что очень жаль, потому что это так естественно.
Суреш Венкат
2
Вы сталкиваетесь с подобной проблемой в биоинформатике: учитывая набор потенциально / возможно, перекрывающихся, случайно созданных подстрок строки, намного длиннее, чем отдельные части; вычислить исходную строку. (секвенирование генов)
Рафаэль
38

Суммы задачи с квадратными корнями: для двух последовательностей и b 1 , b 2 , , b n натуральных чисел A : = i a1,a2,,anb1,b2,,bn меньше, равно или большеB:=iA:=iai ?B:=ibi

  • У проблемы есть тривиальный алгоритм времени в реальном ОЗУ - просто вычислите суммы и сравните их! - но это не подразумевает членство в P.O(n)

  • Существует очевидный алгоритм конечной точности, но неизвестно, достаточно ли полиномиального числа битов точности для правильности. (Подробнее см. Http://maven.smith.edu/~orourke/TOPP/P33.html .)

  • Теорема Пифогора подразумевает, что длина любой многоугольной кривой, вершины и целочисленные конечные точки которой являются суммой квадратных корней целых чисел. Таким образом, проблема суммы корней присуща нескольким задачам плоской вычислительной геометрии, включая евклидовы минимальные остовные деревья , евклидовы кратчайшие пути , триангуляции с минимальным весом и евклидову задачу коммивояжера . (Евклидова проблема MST может быть решена за полиномиальное время без решения проблемы суммы корней благодаря базовой структуре матроида и тому факту, что EMST является подграфом триангуляции Делоне.)

  • Там является полиномиальный вероятностный алгоритм, благодаря Йоханнес Blömer , чтобы решить , являются ли две суммы равны. Однако, если ответ отрицательный, алгоритм Бломера не определяет, какая сумма больше.

  • Вариант решения этой проблемы ( ?) Даже не известен в NP. Тем не менее, алгоритм Бломера подразумевает, что если задача решения находится в NP, то она также в co-NP. Таким образом, проблема вряд ли будет NP-полной.A>B

Jeffε
источник
3
Хороший, мне нравится!
Сянь-Чи Чанг 之 之
Что ж, если мы возьмем только 1000 случайных целых чисел, не слишком больших, то есть около способов разделить их на два набора, поэтому я ожидаю, что две из этих сумм находятся в пределах 900 или более бит друг в друге (и в пределах половины от общей суммы). С другой стороны, найти «худшие» две последовательности для сравнения из этих 2 999 возможностей тоже очень, очень трудно. 29992999
gnasher729
30

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

  • Автоморфизм графа (определите, имеет ли граф нетривиальный автоморфизм). Сводит к графу Изоморфизм, но не известен (не думал?), Что GI-трудно.
  • Групповой изоморфизм и автоморфизм (где группы задаются своими таблицами умножения). Опять же, сводится к графу Изоморфизм, но не считается трудным GI.
  • Кольцевой изоморфизм и автоморфизм. В некотором смысле это дедушка всех вышеперечисленных проблем, поскольку целочисленный факторинг эквивалентен нахождению нетривиального автоморфизма кольца, а изоморфизм графов сводится к кольцевому изоморфизму. См. Нирадж Каял, Нитин Саксена. Сложность проблем кольцевого морфизма. Вычислительная сложность 15 (4): 342-390 (2006). (Интересно, что определение того, имеет ли кольцо нетривиальный автоморфизм, находится в )P
  • Этот пост Билла Гасарха содержит некоторые другие проблемы со вкусом теории Рамси, которые выглядят так, будто они могут быть промежуточными.
  • По теореме Махани никакое разреженное множество не может быть NP-полным. Но мы также знаем , что существуют редкие множества в - P тогда и только тогда N E X P не равно E X P . Таким образом, предполагая, что N E X P E X P , дополненная версия любой N E X P -полной задачи имеет промежуточную сложность. (Такой набор не может быть в P, если N E X P = E X PNPPNEXPEXPNEXPEXPNEXPPNEXP=EXP, противореча нашему предположению.) Существует множество естественных -полных проблем.NEXP
Джошуа Грохов
источник
Мне нравится последний пример. Есть ли у вас какие-либо упоминания об этом?
Маркос Вильягра
1
С.Р. Маханей. Разреженные комплекты для NP: решение гипотезы Бермана и Хартманиса. Журнал компьютерных и системных наук 25: 130-143. 1982. dx.doi.org/10.1016/0022-0000(82)90002-2 Разреженные множества в NP - P, если NEXP neq EXP: Дж. Хартманис, Н. Иммерман, В. Сьюэлсон, Разреженные множества в NP-P: EXPTIME vs. NEXPTIME, Информация и контроль, том 65, выпуски 2-3, май-июнь 1985 г., стр. 158-181. dx.doi.org/10.1016/S0019-9958(85)80004-8
Джошуа
Это хороший список, хотя первые три очень похожи :) Мне также нравится последний пример.
Лев Рейзин
28

Проблема минимального размера схемы (MCSP) - моя любимая «естественная» проблема в NP, которая, как известно, не является NP-полной: учитывая таблицу истинности (размером n = 2 ^ m) m-вариативной булевой функции f, и учитывая число s, f имеет схему размера s? Если MCSP прост, то криптографически безопасной односторонней функции не существует. Эта проблема и ее варианты послужили основной мотивацией для изучения алгоритмов "грубой силы" в России, что привело к работе Левина по NP-полноте. Эту проблему также можно рассматривать с точки зрения ограниченной по ресурсам сложности Колмогорова: вопрос о том, можно ли быстро восстановить строку из краткого описания. Эта версия проблемы была изучена Ко; Насколько я знаю, имя MCSP было впервые использовано Цай и Кабанец. Больше ссылок можно найти в некоторых моих статьях: http://ftp.cs.rutgers.edu/pub/allender/KT.pdf http://ftp.cs.rutgers.edu/pub/allender/pervasive.reach.pdf

Эрик Аллендер
источник
24

Монотонная двойственность

f=f(x1,x2,...,xn)fd=f¯(x1¯,x2¯,...,xn¯)f(x1,x2,...,xn)f=fd

log2nO(log2n/loglogn)O(nlogn/loglogn)

Все еще открыто, находится ли эта проблема в P или нет. Более подробную информацию можно найти в статье 2008 года « Вычислительные аспекты монотонной дуализации: краткий обзор » Томаса Айтера, Казухиса Макино и Георга Готтлоба.

Danu
источник
23

Тривиальность узлов: если замкнутая полигональная цепь в 3-мерном пространстве не является ли она узлом (т. Е. Окружающим-изотопным плоской окружности)?

Известно, что это в NP, благодаря глубоким результатам в теории нормальной поверхности, но не известен ни алгоритм на основе многовременного алгоритма, ни доказательство твердости NP.

Jeffε
источник
1
Возможно, стоит упомянуть, что, как и во многих потенциально NP-промежуточных задачах, известно, что небольшой вариант является NP-полным. А именно, род 3-многообразного узла является NP-полным: если замкнутая многоугольная цепь в триангулированном 3-многообразии и целое число g, является ли узел границей поверхности рода не более g? (Быть несвязанным эквивалентно роду 0.) doi.acm.org.proxy.uchicago.edu/10.1145/509907.510016
Джошуа
Он также содержится в co-AM (Хара, Тани, Ямамото), поэтому не NPC, если не разрушится полиномиальная иерархия.
Питер Шор
3
На самом деле, это все еще открыто. Тасос Сидиропулос нашел ошибку в доказательстве Хара-Тани-Ямамото.
Джефф
coNPcoNP
19

Неизвестно, можно ли за полиномиальное время решить, есть ли у игрока 1 выигрышная стратегия в игре с паритетом (с заданной стартовой позиции). Проблема, однако, содержится в NP и co-NP и даже в UP и co-UP.

Матиас
источник
Можете ли вы дать ссылку? Звучит интересно.
Джошуа Грохов
1
М. Юрдзинский. Определение победителя в Паритетных играх происходит в UP \ cap co-Up. Письма обработки информации 68 (3): 119-124. 1998. Должен быть хотя бы хорошей отправной точкой.
Матиас
Недавняя статья «Алгоритм накачки для эргодических стохастических игр со средним выигрышем с совершенной информацией» также показывает, что даже обобщение игры четности может быть решено за псевдополиномиальное время. В частности, они показывают, что игра под названием BWR game имеет алгоритм псевдополиномиального времени, когда существует постоянное число «случайных узлов». Игра на четность - это случай, когда нет случайных узлов.
Дану
Недавно было показано, что паритетные игры могут быть решены за квазиполиномиальное время, см. Здесь, например.
Томас Климпел
18

Вы получите очень длинный список проблем, если готовы принять проблемы аппроксимации, такие как аппроксимация Max-Cut с коэффициентом 0,878. Мы не знаем, является ли он NP-трудным или в P (мы знаем только NP-твердость, принимая гипотезу Uniuqe Games).

Moritz
источник
Да, это был глупый комментарий, который я начал удалять, как только он был опубликован. Спасибо. :)
Даниэль Апон
Спасибо! Но, думаю, я думал не столько о проблемах аппроксимации, сколько о естественных проблемах.
Лев Рейзин
Возможно, это естественные проблемы, поскольку они соответствуют тому, что достижимо естественным набором методов, в данном случае, полуопределенным программированием.
Мориц
Я предполагаю, что «естественный» является неопределенным критерием ...
Лев Рейзин
18

В монотонной формуле CNF каждое предложение содержит только положительные литералы или только отрицательные литералы. В пересекающейся монотонной формуле CNF каждое положительное предложение имеет некоторую общую переменную с каждым отрицательным предложением.

Решение проблемы


f
f

no(log n)

  • Томас Айтер и Георг Готтлоб, трансверсальные вычисления гиперграфа и связанные с ними проблемы в логике и искусственном интеллекте , JELIA 2002. doi: 10.1007 / 3-540-45757-7_53
Андраш Саламон
источник
17

Вершина подмножества суммы (или равенство сумм подмножеств).

Дано:

akZ>0
k=0n1ak<2n1

S1,S2{1,,n}

jS1aj=kS2ak

Задача о сумме подмножества голубых дыр требует такого решения. Первоначально изложено в « Эффективных алгоритмах аппроксимации для задачи РАВЕНСТВА СУБСЕТА-СУМС» Базгана, Сантхи и Тузы.

оборота user834
источник
16

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

Джо Фитцсимонс
источник
15

Вот проблема в вычислительном социальном выборе, которая, как известно, не находится в P, и может быть или не быть NP-полной.

Контроль повестки дня для сбалансированных турниров с одиночным отбором:

Tn=2ka

Вопрос: существует ли перестановка узлов ( скобка ), так что a является победителем индуцированного турнира одиночного исключения?

Pk2kVTVPk12k1i>0Pk[2i1]Pk[2i]eTPk1[i]=Pk[2i1]e=(Pk[2i1],Pk[2i])Pk1[i]=Pk[2i]PkTPk12kkPk1,,P02k

Контроль повестки дня для сбалансированных турниров с одиночным отбором (составление графика):

Tn=2ka

T2ka

2kxa2k1x2k1yxyk=0

Некоторые ссылки:

  1. Жером Ланг, Мария Сильвия Пини, Франческа Росси, Кристен Брент Венейбл, Тоби Уолш: определение победителя в последовательном голосовании большинства. IJCAI 2007: 1372-1377.
  2. Н. Хазон, П. Е. Данн, С. Краус и М. Вулдридж. Как провести выборы и соревнования. COMSOC 2008.
  3. Тхук Ву, Алон Альтман, Йоав Шохам. О сложности задач контроля графика для нокаут-турниров. AAMAS (1) 2009: 225-232.
  4. Васильевская В. Уильямс. Фиксация турнира. AAAI 2010.
вирджи
источник
13

Взгляните на класс TFNP . У него много проблем с поиском с промежуточным статусом.

Маркос Вильягра
источник
NPcoNP
12

Индуцированная проблема изоморфизма подграфа имеет NP-неполные «левые ограничения», предполагая, что P не равно NP. См. Чен Ю., М. Терли, М. Вейер: Понимание сложности изоморфизмов индуцированного подграфа , ICALP 2008.

Holger
источник
2
Хотя это интересный результат, если вы проверяете документ, в нем даже говорится, что доказательство промежуточной сложности по существу совпадает с теоремой Ладнера, за исключением того, что вы делаете диагонализацию при выборе ограничения LHS. Так что я не знаю, считается ли это «естественной» проблемой, а не просто другой кодировкой теоремы Ладнера.
Джошуа Грохов
Также обратите внимание, что это ограничения источника и цели. Цель (правая сторона) должна иметь особую форму для обеспечения инъективности.
Андрас Саламон
11

NPNP

Задача минимального деления: найдите разбиение множества узлов на две части равного размера, чтобы число пересекающихся ребер было минимальным.

Карпинский, Аппроксимируемость задачи минимального деления на части: алгоритмический вызов

Мухаммед Аль-Туркистаны
источник
у вас есть ссылка на определение проблемы?
Лев Рейзин
Ссылка добавлена.
Мухаммед Аль-Туркистани
10

nv1vβvβ>1

β=nNPcoNPNPPββ=no(1/loglogn)NP

MCH
источник
9

G=(V,E)fvVf(v)e=uvE|f(u)f(v)|f:V{0,1,2,,|E|}{1,2,...,|E|}

  1. Я. Галлиан. Динамический обзор маркировки графиков. Электронный журнал комбинаторики, 2009.
  2. Д.С. Джонсон. Колонка NP-полноты: постоянное руководство. J. Алгоритмы, 4 (1): 87–100, 1983.
  3. Д.С. Джонсон. Столбец NP-полноты. ACM транзакции по алгоритмам, 1 (1): 160–176, 2005.
Александр бондаренко
источник
9

PNPO(nlogn)NPNP

Мухаммед Аль-Туркистани
источник
LOGNPNP[log2n]
8

abax+1b

γ

Гэри и Джонсон в своей оригинальной статье «Компьютеры и неразрешимость» говорят, что (стр. 158-159):

γRMM

RM={x,y:there is a string z such that on input x and guess z M has output y}

L1Σ1γL2Σ2L1γL2MxΣ1yΣ2x,yRMx,yRMxL1yL2MxxxL2xL1

Александр Бондаренко
источник
γ
6

PNPO(nlogn)

Мухаммед Аль-Туркистани
источник
5

Следующей проблемой считается NP-Intermediate, то есть она находится в NP, но ни в P, ни в NP-полной.

Экспонирующая полиномиальная корневая проблема (EPRP)

p(x)deg(p)0GF(q)qr

p(x)=rx
p(x)rxrxr

deg(p)=0

Для получения дополнительной информации см мой вопрос и связанные обсуждения .

Массимо Кафаро
источник
4

Я не знаю, нельзя ли просто показать, что проблема взвешенного гиперграфа изоморфизма, предложенная в ответе Тин Д. Нгуена, является полной GI. Однако существует GI-трудная проблема, тесно связанная с GI, которая еще не была сведена к GI, а именно проблема изоморфизма струн (также называемая проблемой изоморфизма цветов ). Эта проблема на самом деле показана Ласло Бабаи в квазиполиномиальном времени. Он представляет самостоятельный интерес, поскольку он эквивалентен ряду проблем решения в теории (перестановок) групп:

Томас Климпел
источник
3

Проблема, которая, как известно, ни в FP, ни в NP-сложности, заключается в том, чтобы найти минимальное дерево Штейнера, когда вершины Штейнера обещают упасть на два отрезка прямой, пересекающихся под углом 120 °. Если угол между отрезками линии меньше 120 °, тогда проблема NP-трудная. Предполагается, что когда угол больше 120 °, проблема в FP.

Следовательно, следующая проблема решения в настоящее время имеет промежуточную сложность:


q
q

Конечно, на самом деле это может быть в P или NP-полной, но тогда кажется, что у нас будет интересная дихотомия при 120 ° вместо промежуточной проблемы. (Гипотеза также может быть ложной.)

  • JH Rubinstein, DA Thomas, NC Wormald, Деревья Штейнера для терминалов, ограниченных кривыми , SIAM J. Discrete Math. 10 (1) 1–17, 1997. doi: 10.1137 / S0895480192241190
Андраш Саламон
источник