タグ: 多項式時間帰着

← タグ一覧

• P≠NP 予想とは何か：多項式時間・証明書・帰着で計算の壁を測る本クラス P と NP を検証器の言葉で厳密に定義し、多項式時間帰着と NP 完全性から SAT・3SAT・独立集合の関係を証明する。P=NP なら暗号と最適化に何が起きるかまで具体的に示す。情報科学アルゴリズムとデータ構造学部計算複雑性NP完全多項式時間帰着SAT約 64 分