но как мне доказать, что он попадает в NP, а не в exp.время, разрешимые языки или узнаваемый тьюринг?
Вы не можете, потому что это не может произойти.Каждый язык в NP является EXPTIME, разрешим и узнаваем по Тьюрингу.L находится в NP тогда и только тогда, когда существует полином p и язык PTIME L 'такой, что
x в L, если и только если существует y длины p (| x |) такой, что(x, y) находится в L '
Чтобы показать, что NP является подмножеством EXPTIME, обратите внимание, что можно просто выполнить поиск грубой силы для всех возможных y.И каждый ЯЗЫК EXPTIME явно разрешим и распознаваем.
Теперь, что касается вашего вопроса о показе языка L, принадлежащего NP: попробуйте найти способ, которым для каждого x в L вы можете записать«доказательство» или «сертификат», что он принадлежит L. Такой сертификат не должен существовать для x, а не для L, и что этот сертификат является правильным, он должен быть эффективно проверяем (за полиномиальное время).Длина сертификата должна быть максимально полиномиальной по длине x.
Как именно это сделать, конечно, зависит от конкретного языка L.Многие задачи NP сформулированы как проблемы поиска (существования): имеет ли этот граф гамильтонов цикл, имеет ли эта булева формула удовлетворительное присваивание и так далее.В этом случае выбор сертификата, как правило, очевиден, можно взять сертификат за искомую вещь (путь Гамильтона или само выполнение назначения).Нужно проверить, что с учетом графа и предполагаемого гамильтонова пути можно проверить, является ли он на самом деле гамильтоновым путем за полиномиальное время, или по формуле и предполагаемому удовлетворительному назначению можно проверить, действительно ли это удовлетворительное назначение в полиномевремя.Обычно это легко показать.
Обратите внимание, что P является подмножеством NP (просто возьмите что-нибудь для сертификата, средство проверки сертификатов может решить саму исходную проблему за полиномиальное время).Язык, который вы просили, {a ^ nb ^ nc ^ n |n> = 0} довольно легко в P (и, следовательно, в NP).