Есть ли проблемы с решением, которые можно решить, но не в NP ? [закрыто]

Закрыть г. Этот вопрос не по теме . В настоящее время он не принимает ответы.

Хотите улучшить этот вопрос? Обновите вопрос , чтобы он был по теме для Stack Overflow.

Закрыт 8 лет назад .

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

Существуют ли проблемы решения, которые разрешимы, но не в NP?
Если да, то проблемы, требующие решения, сложнее, чем эквивалентная проблема решения?

Я подозреваю, что ответ на первый вопрос является громким «да», и что ответ на второй - громкое «нет».

В первом случае пример проблемы может быть «дан набор S, подмножество T из S и функция f с областью определения 2 ^ S, определите, максимизирует ли T f ". Для общих S, T и f вы даже не можете проверить это, не проверив f (X) для всех подмножеств X из S, верно?

Во втором случае ... ну, я признаю, что это больше предчувствие. По какой-то причине не похоже, что должно иметь значение, содержит ли ответ один бит (для задач решения) или любое (конечное) количество бит ... или, другими словами, почему вы не должны иметь возможность учитывать символы, оставшиеся на ленте после остановки TM как часть «ответа».

EDIT: Собственно, у меня вопрос ... как точно ваша конструкция показывает, что функциональные задачи «не сложнее», чем задачи решения? Во всяком случае, вы показали, что ответить на функциональную проблему не легче, чем на проблему решения ... что тривиально. Возможно, это моя вина, что я задаю вопрос небрежно.

Учитывая TM T1 в NP, который решает проблему «Является ли X решением проблемы P» для переменной X и (для аргументации) фиксированный P, Гарантируется ли, что в NP будет TM T2, который останавливается везде, где останавливается T1, который заканчивается в состоянии «остановить принятие» везде, где он останавливается, и уходит, например двоичное представление X на ленте?

complexity-theory np

задан aegrisomnia 15 July 2011 в 20:59

0 ответов

Другие вопросы по тегам:

complexity-theory np

Есть ли проблемы с решением, которые можно решить, но не в NP ? [закрыто]

0 ответов

Похожие вопросы: