Решение проблем, которые не могут быть решены даже эффективно?

Question

Как эти проблемы попадают в гобелен из комплектов P, NP, NP-Hard и т. Д.? Я не знаю, существуют ли вообще такие проблемы, но то, что инициировало мой мыслительный процесс, было размышлением о разрешении проблемы коммивояжера:

    Given a list of cities and the distances between each pair of cities, and a 
    Hamiltonian path P, is P the shortest Hamiltonian path?

Я подозреваю, что мы не можем проверить "краткость" P за полиномиальное время, в котором эта проблема решения отсутствует даже в NP. Так, где это падает в этом случае?

Answer 1

Даны два целых числа n и m, есть ли ровно m простых чисел p <= n?

Это может быть решено примерно за O (n^(2/3)) и, возможно, немного быстрее, но размер проблемы, конечно, не n, а log (n), поэтому требуется сублинейное время по n, но экспоненциальное время по размер проблемы. Это не хуже, чем вы ожидаете от проблемы в NP. Однако я не вижу никакой возможной информации, которая позволила бы вам проверить это быстрее.

(На самом деле, существует алгоритм, который определяет число простых чисел <= n примерно за O (n^(2/3)) шагов, но нет известного алгоритма, который мог бы проверить ответ быстрее, чем найти ответ.)

Answer 2

При заданных целых числах n и k 2^n - 1 является k-м простым числом Мерсенна?

Можно доказать, что p является простым по времени полиномом размера p, если известна полная факторизация p + 1, а если p = 2^n - 1, то полная факторизация p + 1 тривиальна.

Тем не менее, это полиномиальный размер р. 2^n - 1 можно проверить на простоту во времени, полиномиально от n. Тем не менее, это не полиномиальный размер задачи, который будет примерно равен числу цифр в n и k. И это просто ответило бы на вопрос, является ли 2^n - 1 простым числом Мерсенна. Чтобы доказать, что это k-е простое число Мерсенна, нам нужно проверить 2^m - 1 при 1 <= m

В настоящее время ответ на вопрос неизвестен для k >= 44 и многих 8-значных значений n.

Answer 3

Эта проблема в со-НП. Вы можете думать о НП как о классе проблем, где, если ответ "да", я могу дать вам небольшое количество информации, которая убедит вас в этом. Например, проблема

Есть ли в G гамильтонов цикл с ценой не более k?

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

Класс co-NP состоит из проблем, когда, если ответ " нет", я могу дать вам небольшое количество информации, которая убедит вас в этом. В вашем случае предположим, что нет, P не является кратчайшим гамильтоновым путем. Это означает, что есть более короткий путь P'. Если бы я дал вам P ', вы могли бы легко проверить, что P не был идеальным. Придумать P может быть очень сложно (на самом деле, это со-NP-сложно!), Но как только вы его получите, довольно просто использовать его, чтобы подтвердить, что ответ - нет.

Надеюсь это поможет!