NP-Hard решение вопроса

Question

У меня NP трудная проблема. Давайте представим, что я нашел некоторый полиномиальный алгоритм, который находит ТОЛЬКО одно из многих существующих решений этой проблемы, но по крайней мере одно решение (если оно присутствует в тесте). Этот алгоритм рассматривается как решение вопроса NP = P (если этот алгоритм преобразован в математическое доказательство)?

Спасибо за ответы

Answer 1

NP - это класс решения задач.Ваш алгоритм должен отвечать «да» или «нет» правильно на все возможные случаи (вопросы).

Например, проблема: «заданный граф G и число k, содержит ли G клику размера> = k"NP-жесткий.Если у вас есть алгоритм полиномиального времени, который каждый раз правильно отвечает «да» или «нет», то он является действительным доказательством P = NP.Алгоритм не должен явно показывать клику - только ответ , если , он существует для всех возможных G и k.

Answer 2

Если вы обнаружите NP-сложную проблему и сможете обнаружить некоторые дела, которые вы можете решить за полиномиальное время (оставив другие на экспоненциальном времени), то только в том случае, если доля оставшихся дел находится в порядке log (N) / N вы измените порядок всей задачи, и даже тогда, только если вы можете ограничить свой экспоненциальный случай проверкой только log (N), а не всех возможностей N.

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