プルーフアシスタントでP対NPを述べるのはどのくらい困難ですか？

Question

GJ Woegingerリスト116 PとNPの問題の証明。Scott Aaronson公開 " "誰かがPとNPを決済しようとしているたびに。いくつかの研究者氏はを拒否します.P対PversusNP "質問。

私は3つの関連質問をしています：

1. PVの証明が正しいかどうかを確認することができる証拠補助者を使用していないのはなぜですか？
2. 最初の場所でプルーフアシスタントでP対NPを述べる努力や努力がどのくらい努力していますか？
3. 現在、P対NP証明を検証することができる原則として少なくとも何らかのソフトウェアがありますか？

Answer 1

私はDWに同意しません。私はそれがプルーフアシスタントで述べられているP対NPの結果のために可能である（困難であるが）可能性があると思います。また、彼らが非常に評判の良いソース。

特に、リソースDW状態はどれもタイプの理論に基づいていません。これはプルーフアシスタントのための非常に有望な方向です。 COQはとりわけ4色の定理の証明を形式化してください。いくつかの重い数学的持ち上げが可能です。

あなたの特定の質問に答えるために：

1. 主な理由は、定理のコミュニティでは、定理の社会が広く受け入れられていないことです。彼らが努力する学習、そして数学者はしばしば基礎となる技術（タイプ理論、建設的数学など）の懐疑的です。 しかし、カテゴリ理論、プログラミング言語理論、正式なロジックなどのように、大規模な開発者がプルーフアシスタントで正式化されていることで、主要な研究者が非常に快適である分野があります。そのため、固有の実現可能性の問題としての文化的問題があると思います。

   それ以外の理由は、これまでのところ、目立った「証明」の大部分がクランクによって行われており、それは不可避的に欠陥を明らかにするので彼らの結果を正式にしたくない。

2. プルーフアシスタントでP対NPをまったく難しくない。チューリングマシンを使用することはできますが、誘導性ファミリーを使用して小さなステップセマンティクスをモデル化するための簡単なチューリング完全なプログラミング言語をモデル化しやすく、プログラムが取るステップ数として実行時を定義しやすくなります。多項式のステップ数で停止したプログラムによって受け入れられた言語として、 $ p $ を定義でき、 $ np $

   編集：それは既存のテクニックがあります< / a>は、アルゴリズムが定理証明書の多項式時間で実行されることを示す。したがって、これは、NPハード問題のためのポリ時差アルゴリズムを示すため、またはそのようなアルゴリズムの存在との矛盾を導き出すために使用され得る。

3. このような証明を検証することができるソフトウェアのトン>は、そのソフトウェアを使用して証明書を書き込んだ場合にが表示されています。私が最も株式を置く2つの候補者は、 coq と LEAN 。特にCOQは数学におけるいくつかの主要な結果を検証するために使用されてきました。

Answer 2

この目的のための証拠補助人を使用することは、原則として確かに可能であるが、私はそのような証明書を書くのが最も多くの人々よりも多くの努力がかかると思われる。それはの著者からかなりの努力を必要とするでしょう。 PURPORTED P対プールを正式化して、証明を正式化しました。

は、人間の証明書を証明アシスタントが検証できるフォーマットに翻訳することは面倒で時間がかかりました。私は、人間が書かれた証明の1ページに1週間から週の努力の見積もりを見ました。それから、証明が構築している以前の結果をすべて正式化しなければなりません。 PVの証明の試みを見ると、それらは典型的には事前の論文から多くの先進的な機械および既存の結果を使用するが、これは形式化される必要があるだろう。

これにより、これまでに見た純粋な証明の種類のために、提案されている新しい証明とそれが頼っているすべての以前の結果の証明の両方を正式に適用することが完全に実用的ではないでしょう。 user21820を指す、より実用的なものは、頼っているすべての以前の結果の声明のみを正式化することですが、証明には正式に正式化することです。したがって、定理 $ t $ を証明するのではなく、 $（x \ land y \ land）を正式にしました。 \ cdots）\はT $ を意味します。ここで、 $ x、y、\ dots $ は、証明が依存する前の結果です。これはNP完全性の結果を十分に検証することに短いですが、人々が以前の結果を信じるならば、それは人々が新しい結果に自信を得ることを可能にするでしょう。これは、 $ t $ の全証を形式化するよりも現実的なものになるでしょう。 $ x、y、\ dots $ 、それらの以前の結果の証明を形式化するための努力よりはるかに小さいです。

それでも、このトリックであっても証明を正式にするために挑戦的で些細な努力を要求することが必要です。

形式化され正式に検証された数学とコンピュータサイエンスの定理の既存のライブラリを見ることができます。 http： //us.metamath.org/ と http://formalmath.org/ と https://www.isa-afp.org/topics.html と http://mizar.org/library/ 。あなたは特徴付けられているものが基本的な学部資料に関するものであることに気付くかもしれません。私たちは、大学院レベルで教えられたすべての定式化のための遠くの方法で、大学院レベルで教えられたものではなく、新しい研究成果をもってください。

詳細については、 https://math.stackexchange.com/q/792010/14578 https://math.stackexchange.com/q/113316/14578 と https://math.stackexchange.com/q/1767070/14578 https://math.stackexchange.com/q/2747661 / 14578 http://www.ams.org/notices/200811/tx081101370p.pdf 。

Answer 3

I can give a direct answer to (2): $P\ne NP$ has been stated in Lean (along with the other main results of Cook's paper, where the conjecture was first described), as part of the Formal Abstracts project.

Answer 4

I believe your question is not that much of a proper theory question, so with your permission I'll give it a not-so-technical answer.

Why are people not using proof assistants that could verify whether a proof of P vs. NP is correct?

Because CS theorists rarely (perhaps extremely rarely) write proofs in machine-verifiable form.

How hard or how much effort would it be to state P vs. NP in a proof assistant in the first place?

Very hard at least in the "uninteresting" sense that @DW explained; but it could be anywhere from easy to impossible in the "interesting" sense of expressing the concepts in a proof, if it were to exist.

But you know, this will never happen because:

1. Until a proof is found it can't be done anyway
2. You have to know the proof like the back of your hand to convert it into machine-verifiable form.
3. ... and when enough people know the proof, they will either have found a flaw or be satisfied that it's valid and not care about machine-checking it.

Is there currently any software that would be at least in principle capable of verifying a P vs. NP proof?

I'm not well-versed enough in proof verification software to comment about what's actually implemented, but it's probably nearly-impossible to answer your question, because - who knows what form such a proof will take? And thus - how would you know, now, if it's expressible in such a way that your proof verifier can process?