Этот язык есть в NP?

L={[G, K] | G is a simple undirected graph with no simple path longer than k}

(Далее, это Со-НП)?

Я считаю, что это НП. Я мог бы предоставить верификатор, который делал следующее:

V(G,E, k) — верификатор, где G — граф, E — список ребер для графа, а k — указанный путь.

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

Где недостатки в моем мыслительном процессе?


graph math path-finding np complexity-theory
person h4x0rjax    schedule 02.04.2014    source источник
comment
Вы имеете в виду путь без повторения узла не более чем k?   -  person Codor    schedule 02.04.2014
comment
Да, допустим, это простой путь. Редактирование вопроса сейчас;   -  person h4x0rjax    schedule 02.04.2014

Ответы (1)


arrow_upward
2
arrow_downward

Дополнением к вашей задаче L, назовем ее L', является "дан граф G=(V,E) и целое число < em>k, содержит ли G простой путь длины не менее k+1'', что является известной проблемой LONGEST-PATH. Проблема L' явно связана с NP: просто угадать путь, если он есть. (То же самое, если задан путь, просто убедитесь, что его длина действительно не меньше k+1.) Обратите внимание, что проблема находится в coNP тогда и только тогда, когда ее дополнение находится в NP, что означает, что L находится в coNP.

Поскольку LONGEST-PATH является NP-полным, L не находится в NP, если только coNP=NP. (Поскольку мы считаем, что coNP != NP, это означает, что никакая NP-полная проблема не может принадлежать coNP и никакая coNP-полная проблема может принадлежать NP. См. книгу Арора-Барак для подробностей.)

person blazs    schedule 02.04.2014