問題タブ [p-np]

P=NP かどうかという問題は、おそらくすべてのコンピューター サイエンスで最も有名です。どういう意味ですか？そして、なぜそれはとても興味深いのですか？

ああ、そして追加の信用のために、声明の真実または虚偽の証拠を投稿してください. :)

特定の NP 完全問題に対する多項式時間アルゴリズムでしょうか、それとも NP 完全問題の解決策を示す抽象的な推論が存在するのでしょうか?

特定のアルゴリズムの方がはるかに役立つようです。これにより、NP 問題を多項式で解くために必要なことは、証明が解を持つ特定の NP 完全問題に変換することだけです。

パスワードを回復しようとしました。このことを考えたとき、「パスワードの回復」という問題が NP 問題の非常に良い例であることに気付きました。パスワードがわかっている場合は、多項式時間で簡単に確認できます。しかし、パスワードがわからない場合は、指数関数的な時間がかかることが示される可能性のあるソリューションの全領域を検索する必要があります。

ここで私の質問は次のとおりです。「パスワードの回復」は、実行に多項式時間以上を必要とすることが示される NP の要素であるため、これは P != NP であることを示していませんか?

P = NPは今のところ解決されていないことは知っていますが、次のことについて誰かに教えてもらえますか。この問題に取り組むのに役立つ可能性のある、現在最も有望な数学的/コンピューター科学的方法は何ですか。それとも、これまでに役立つ可能性があることが知られているそのような方法はありませんか？この分野で行われた研究のすべて/ほとんどを見つけることができるこのトピックに関する（無料の）概要はありますか？

最近、HP研究所のVinay Deolalikarが、P！=NPであることを証明したと主張する論文が浮かんできました。

誰かがこの証明が数学的にあまり傾いていない私たちのためにどのように機能するかを説明できますか？

ウィキペディアの記事を読みましたが、正確に NP 問題とは何かを理解できませんでした。誰か私にそれらについて教えてもらえますか? また、それらと P 問題との関係は何ですか?

本当に.. 今週の火曜日に卒業のための最後のテストがあります. NP問題の解は多項式時間で検証できることに気づきました。しかし、決定論はそれと何の関係があるのでしょうか?
そして、NP-complete と NP-hard の名前の由来を説明できれば、それは素晴らしいことです (私はそれらの意味を理解していると確信しています。それは）。
些細なことで申し訳ありませんが、私には理解できないようです (-:
ありがとうございます!

私の理解では、すべての NP 完全問題は NP 困難ですが、一部の NP 困難問題は NP 完全ではないことが知られており、NP 困難問題は少なくとも NP 完全問題と同じくらい困難です。

それは、NP完全ではないNP困難な問題がより困難であることを意味しますか? そして、それはどのように難しいですか？

エミュレーターとステートメントに関する投票数の多い質問を読んでいたところです

特定のバイナリ内のすべてのコードを見つけることは、停止問題と同等であることが証明されています。

本当に私に突き出ました。

そんなことはあり得ませんよね？それは単なる大きな依存関係グラフではありませんか?

この声明へのさらなる洞察に本当に感謝します。

複雑さと問題解決に関する400レベルのクラスを受講しています。最後のプロジェクトは、PとNPに関係する問題を実装することです。残念ながら、先生はプロジェクトの境界について許しがたいほど漠然としています。

ですから、私が実装する可能性のある中程度に難しい問題について誰かが提案を持っているかどうかを確認するために、ここで質問したいと思いました。この質問はかなり曖昧だと思いますが、誰かが好きな問題を抱えているかどうか聞いてみたいと思います。

ありがとう！