問題タブ [p-np]

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

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

ありがとう！

FindBugs特定のプログラム/コードベースで無限に終わることのないループを検出できるというツールがあります。

これFindBugsは、コードを分析することで、プログラムが終了するかどうかを検出できることを意味します。停止問題は、次のことを定義する問題です。

任意のコンピュータ プログラムの説明を与えられて、そのプログラムが実行を終了するか、永久に実行し続けるかを決定します。

これは、停止問題が解決されたこと、または停止問題のサブセットが解決されたことを意味するのでしょうか?

すべての SolvePnP の可能性の間で精度と時間を比較しようとしています: CV_ITERATIVE、CV_EPNP、および CV_P3P

また、結果を Matlab EPNP と比較しました。

そして、EPNP と P3P が失敗したように見えます:

ください ：

ITERATIVE : 回転行列 : [1, -2.196885546074445e-016, 9.692430825310778e-016; 2.196885546074445e-016、1、1.012059558506939e-015; -9.692430825310778e-016、-1.012059558506939e-015、1]

ITERATIVE : 翻訳ベクトル : [71.42857142857143; -151.4285714285714; 500]

P3P : 回転行列 : [1, 0, 0; 0、1、0; 0、0、1]

P3P : 翻訳ベクトル : [-3.97771428571427e-015; -4.022285714285698e-015; 9.989999999999962e-017]

EPNP : 回転行列 : [1, 0, 0; 0、1、0; 0、0、1]

EPNP : 翻訳ベクトル : [-3.97771428571427e-015; -4.022285714285698e-015; 9.989999999999962e-017]

なにか提案を ？

アレクサンドル・コーンマン

次の 2 つのステートメントがあります。決定問題 A が決定問題 B に多項式時間で還元可能であり (つまりA≤ pB)、B が NP 完全である場合、A は NP 完全でなければなりません。

と：

決定問題 B が決定問題 A (つまりB≤ pA) に多項式時間で還元可能であり、B が NP 完全である場合、A は NP 完全でなければなりません。

上記の記述のうち、正しいものはどれですか?

解説もお願いできますか？

NP Complete の正式な定義を理解しようとしていますが、いくつか質問がありました。誰かがより多くの洞察を提供できるかどうか疑問に思っていました。

Jon Kleinberg アルゴリズムの本では、すべての NP 問題を問題 X に還元できる場合、問題 X は集合 NP 完全に含まれると述べています。

P は NP のサブセットであるため、P の問題を多項式時間で NP 完全問題に還元できることになります。これは、リダクションが多項式時間で行われるため、この NP 完全問題を多項式時間で解くことができるという矛盾につながります。これは真実ではありません。したがって、この推論のどこが間違っているのかわかりません。

また、多項式時間で NP 問題を NP 完全に還元できるのであれば、なぜ NP 完全が難しいと言えるのでしょうか。リダクションは多項式時間で行われるため、漸近的に言えば、違いはありません。