computer-science - 言語がNPに該当するかどうかをどのように判断しますか？

Question

たとえば、私はその言語を知っています

CFLのポンピング補題によって文脈自由ではありませんが、expではなくNPに分類されることをどのように証明しますか。時間、決定可能な言語、または認識可能なチューリング？

編集：いくつか掘り下げました、そして私がした一つの見落としは、NPの問題は非決定性チューリングマシンによって多項式時間で検証可能な問題であるということです。どうすればわかりますか：a：多項式時間でこの言語に存在するベリファイアがあり、b：NDTMがそれを認識できます

Answer 1

しかし、それがexpではなくNPに該当することをどのように証明しますか。時間、決定可能な言語、または認識可能なチューリング？

それは起こり得ないので、あなたはできません。NPのすべての言語は、EXPTIMEにあり、決定可能であり、チューリングで認識できます。Lは、多項式pとPTIME言語L'が次のように存在する場合にのみNPに含まれます。

（x、y）がL'にあるような長さp（| x |）のyが存在する場合に限り、Lにx

NPがEXPTIMEのサブセットであることを示すために、すべての可能なyに対してブルートフォース検索を実行できることに注意してください。そして、すべてのEXPTIME言語は、明らかに決定可能で認識可能です。

さて、言語LがNPに属することを示すことについてのあなたの質問については、Lの各xについて、それがLに属することの「証明」または「証明書」を書き留めることができる方法を考え出すようにしてください。 Lにないxの証明書は存在しないはずであり、この証明書が正しいことは（多項式時間で）効率的に検証できる必要があります。証明書の長さ自体は、最大でxの長さの多項式である必要があります。

もちろん、これをどのように行うかは、特定の言語Lによって異なります。多くのNP問題は、検索（存在）問題として表現されます。このグラフにはハミルトン閉路がありますか、このブール式には満足のいく割り当てがありますかなど。この場合、証明書の選択は通常明確であり、証明書を検索対象（ハミルトンパスまたは満足のいく割り当て自体）と見なすことができます。グラフと疑わしいハミルトンパスが与えられた場合、それが実際に多項式時間のハミルトンパスであるかどうかを確認できるか、式と主張された満足のいく割り当てが与えられた場合、それが実際に多項式の満足のいく割り当てであるかどうかを確認できることを確認する必要があります時間。これは通常、簡単に表示できます。

PはNPのサブセットであることに注意してください（証明書に何でも取るだけで、証明書チェッカーは元の問題自体を多項式時間で解決できます）。あなたが求めた言語、{a ^ nb ^ nc ^ n | n> = 0}は、P（したがってNP）では非常に簡単です。