2009-04-18から1日間の記事一覧
PとNPが等しい、または等しくないという主張を形式化した文が体系に依存して構成されるものだとすると、P対NP問題を形式的体系内で解決することは難しいのではないかと思います。 ゲーデルの第二不完全性定理の証明に使われる証明可能性述語はまさに体系に依…
PとNPが等しい、または等しくないという主張を形式化した文が体系に依存して構成されるものだとすると、P対NP問題を形式的体系内で解決することは難しいのではないかと思います。 ゲーデルの第二不完全性定理の証明に使われる証明可能性述語はまさに体系に依…