0

言語のメンバーシップを決定しようとする非決定性マシンには、メンバーシップを証明するヒント（「証人」または「証明書」と呼ばれる）が表示されます（言語外の要素にはそのような証人は提供されません。定義は非対称です）。

したがって、非決定論的アルゴリズムがO（f（n））時間の問題を解決できる場合、これは証明書の長さがf（n）であることを意味しますか？そして、入力サイズはn？

また、O（f（n））時間で証明書を検証できるアルゴリズムAが存在する場合、これは、O（f（n））時間で問題を解決できる非決定論的アルゴリズムの存在をどのように意味しますか？

4

1 に答える 1

0

私見では：

  • では、非決定論的アルゴリズムが O(f(n)) 時間で問題を解決できる場合、これは証明書の長さが f(n) であることを意味するのでしょうか?

番号

  • 入力サイズはnですか？

はい

  • また、O(f(n)) 時間で証明書を検証できるアルゴリズム A が存在する場合、これは O(f(n)) 時間で問題を解決できる非決定論的アルゴリズムの存在をどのように意味しますか?

ここには何の意味もありません。ステートメントは、非決定論的アルゴリズムが O(f(n)) の問題を解決でき、解決策 (必要に応じて証明書またはホワイトネス) が O(g(n)) で検証でき、f と g が多項式である場合です。 、より問題は NP ハードです。(必ずしも NP 完全であるとは限りません)

于 2012-08-27T20:51:01.450 に答える