Как можно проверить задачу коммивояжера за полиномиальное время?

Так что я понимаю идею, что решение проблемы определяется как

Есть ли путь P такой, что стоимость ниже, чем C?

и вы можете легко проверить это, проверив полученный вами путь.

Однако что, если нет пути, который соответствует этим критериям? Как бы вы проверили ответ «нет», не решив проблему TSP с наилучшим путем, и обнаружив, что лучший вариант имеет худшую стоимость, чем C?

complexity-theory time-complexity np decision-problem traveling-salesman wjmccann
источник

Лично я только слышал, что класс NP означает проверку по времени, но никогда не видел ограничения, которое означает только проверку ответов «да, вот решение». Кажется интуитивно понятным представить, что вы должны быть в состоянии проверить любое решение в поли-времени.

wjmccann

Ответы:

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

Класс задач, где вы можете проверить «нет» экземпляров за полиномиальное время, является co-NP . Любой язык в co-NP является дополнением к некоторому языку в NP , и наоборот. Примеры включают такие вещи, как не-3-окрашиваемость. Проблема, которую вы описываете: «Нет ли пути TSP с длиной не более ?» также в co-NP : если вы уберете двойное отрицание, экземпляр «нет» для этой проблемы будет экземпляром «да» для TSP, и мы можем проверить их за полиномиальное время. $C$

Есть некоторые проблемы, такие как целочисленная факторизация и любая проблема в P , которые, как мы знаем, существуют как в NP, так и в co-NP . (Спасибо user21820 за указание на это.)

Неизвестно, являются ли NP и co-NP одним и тем же набором проблем. Если они одинаковы, то мы можем проверить как «да», так и «нет» экземпляры TSP. Если они разные, то P $\,\neq\,$ NP , так как мы знаем, что P $\,=\,$ co-P (потому что мы можем просто отрицать ответ детерминированной машины, давая ответ на проблему дополнения).

Дэвид Ричерби
источник

Возможно, стоит упомянуть, что нам известны некоторые проблемы как в NP, так и в coNP, но мы не знаем, есть ли они в P или нет, например, целочисленная факторизация.

user21820

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

Касперд

@kasperd: общеизвестный факт, что целочисленная факторизация, когда она превращается в задачу решения (есть ли у n простой множитель меньше m?), присутствует как в NP, так и в coNP (оба экземпляра да / нет можно проверить за полиномиальное время с помощью тест на простоту AKS с учетом первичной факторизации в качестве сертификата), но пока еще не показан в P.

user21820

@ user21820 Есть намного более простые и быстрые способы проверки факторизации, чем AKS.

Касперд

@kasperd: Мне было бы интересно вот это. Чтобы проверить факторизацию, вам понадобятся, например, простые факторы, а для каждого простого фактора - доказательство того, что оно является простым.

gnasher729

«Как можно проверить задачу коммивояжера за полиномиальное время?»

Либо так, как вы описываете, либо не существует такого способа.

«Однако, что, если нет пути, который соответствует этим критериям?»

В этом случае для всех машин NP для решения проблемы машина выдаст no для всех сертификатов-кандидатов.

«Как бы вы проверили ответ« нет », не решив проблему TSP с наилучшим путем, и выяснив, что лучший вариант имеет худшую стоимость, чем C?»

Ну, можно получить интерактивное доказательство того, что таких путей нет .

Неизвестно , что описанная вами проблема, TSP, связана с coNP , поэтому не существует "NP-подобного" способа проверки отсутствия такого пути.

Юхо
источник