Есть ли в NP-Hard задачи решения, решение которых не поддается проверке за полиномиальное время?

Прохожу классы сложности. Необходимо уточнить проблемы с NP_Hard.

Спасибо, Хариендра.


np-hard complexity-theory
person hareendra reddy    schedule 27.08.2013    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Задачи, проверяемые за полиномиальное время, находятся в NP. NP является правильным подмножеством NEXPTIME. Следовательно, NEXPTIME\NP не пусто, и его проблемы не поддаются проверке за полиномиальное время. По определению задачи в NEXPTIME\NP являются NP-сложными.

См. раздел Википедия — EXPTIME.

person Oswald    schedule 27.08.2013