{0,1}^nの半分の文字列を持つNFA

Question

言語L（M）が{0,1} *のサブセットであるNFA Mがある場合、L（M） n> = 0の{0,1}^nの文字列の半分以下がNP-hardです。

Answer 1

まず、提案している問題が実際に解決可能かどうかを判断する必要があります。

実際にNFAで解くことができると仮定すると、対応するTuring Machine（TM）によって確かに解決できます。

レッツのL（TM）= L（M）

は次に、問題の所与のセットのためのソリューションを確認することができ決定性チューリングマシンが存在します。したがって、問題はNPです。

あなたの質問によると、L（M）が{0,1}^nのn> = 0の文字列の半分より少ないかどうかを判断するために、問題は決定可能であり、P型。

したがって、多項式時間で既にNP-Hardと証明されている別の問題に変更できるアルゴリズムを使用することで、NP-Hardであることを証明できます。

アルゴリズムを定式化するために必要なデータがありません。