演習テストを実行して、CS 理論試験の準備をしています。この問題では、言語が属する「ゾーン」を (RL/DFSA/NFSA)/(CFG/CFL/NPDA)/(NP)/(EXPTIME)/(DL/DTM/NDTM)/( TR) そして、言語が (CFG/CFL/NPDA) ゾーンを超えることを証明する方法がわからないことに気付きました。ここに 2 つの問題 (3 と 5) がありますが、それらは文脈自由言語のポンピング レンマに失敗するため、そのゾーンに入ることはできません。
編集: 答えは、3 と 5 の両方が NP に分類されるということですが、なぜですか?
あなたは、3 と 5 が NPDA ゾーンにないことを証明できると述べました。そこからピックアップ。次の NP に進みます。ここから先は、さまざまに制限されたチューリング マシンを使用します。
対数空間を持つ線形時間で言語 3 を認識できます。a 記号を数えます。b シンボルを数えます。c 記号を数えます。カウントを比較します。これは、データの線形スキャンと 2 進数の比較です (これは、入力長の線形時間よりも短くなります)。線形時間は NP のサブセットです。教授はどの程度詳細に説明することを要求しますか (つまり、カウントを区切るために 3 番目のアルファベット記号を明示的に導入する必要がありますか? 2 進数の比較方法を詳しく説明する必要がありますか?)?
5 を解くには、2 進数の乗算の限界を知る必要があります。aを数え、bを数え、cを数えます。a の数に b の数を掛けます。結果を c のカウントと比較します。これは、入力に加えて、バイナリ乗算の複雑さが何であれ、線形スキャンです (ただし、乗算する数値は log(n) ビットであることを忘れないでください)。あなたのゾーンはそれほど制限的ではないので、少なくとも多項式時間に拘束されているとしましょう. P は NP の部分集合なので、そこにいます。
これよりも高い場合は、問題の詳細な説明が得られると思います。PSPACE が EXPTIME ゾーンにあると仮定します。頭に浮かぶ標準的な例は、定量化されたブール式です。これは SAT に似ています (クックの定理は、SAT が NP 困難であることを証明しています) が、量指定子を使用します。QBF が PSPACE 完全であることを示す優れた証明があり、これはクックの定理に非常によく似ています。明らかに別のゾーンのサブセットに属していないコンテキスト依存言語もここに属していると思います (言語のプロダクション ルールの説明を取得する場合)。
次のゾーンは停止するチューリング マシンです。アルゴリズムを説明できれば、どんなにばかげていても (そして、それがばかげているに違いないか、以前のゾーンでキャッチされていたはずです)、ここで終了できます。
次のゾーンは、ライスの定理に関するものです。その悪い男の子をウィキします。すべての証明は、ライスの定理を使えば簡単です。このゾーンは、最初のゾーンの正規表現または FSA を考え出すよりも簡単です。