Formal definition of NP
It is traditional to view NP as the class of languages whose elements posses short proofs of membership. A “proof that z∈ L ” is a witness wz such that PL(z,wz)=l,where PL is a polynomial-time computable Boolean predicate associated to the language L such t hat PL(z, y)=0 for all y if z is not in L . The witness must have length polynomial in the length of the input z , but needs not be computable from x in polynomial time. A slightly different point of view is to consider NP as the class of languages L for which a powerful prover may prove membership in L to polynomial-time deterministic verifiers. The interaction between the prover and the verifier, in this case, is trivial: the prover sends a witness (“proof”) and the verifier computes for polynomial time to verify
that it is indeed a proof.
NPは、要素がメンバーシップの証明を簡潔に持つ言語のクラスとして捉えるのが一般的です。「z∈Lの証明」とは、PL(z,wz)=lとなるような証拠wzのことです。ここで、PLは言語Lに関連付けられた多項式時間で計算可能なブール述語であり、zがLに含まれない場合、すべてのyに対してPL(z,y)=0となります。証拠の長さは入力zの長さの多項式である必要がありますが、xから多項式時間で計算可能である必要はありません。少し異なる視点としては、NPを、強力な証明者が多項式時間で決定論的な検証者に対してLへのメンバーシップを証明できる言語Lのクラスと考える方法があります。この場合、証明者と検証者の間のやり取りは単純です。証明者は証拠（「証明」）を送信し、検証者は多項式時間で計算して、それが確かに証明であることを検証します。
https://scispace.com/pdf/how-to-prove-all-np-statements-in-zero-knowledge-and-a-4l3wxo6n8y.pdf
The Complexity of Theorem-Proving Procedures Stephen A. Cook
https://dl.acm.org/doi/epdf/10.1145/800157.805047
Универсальные задачи перебора
https://www.cs.bu.edu/fac/lnd/dvi/ppi9-115.pdf
Universal Search Problems:Problems of Information Transmission, Vol. 9, No. 3, pp. 265–266
Crossover Gadget Planar Formulae and Their Complexity David Lichtenstein 1982
https://dl.acm.org/doi/10.1137/0211025
あらゆる数学的な宣言は3-colorに変換でき、3-color塗り分けできるならNP-complete、そうでないならfalse statementということになる。この場合、連鎖パターンはせいぜい6種類であり、平面3-SATと立体3-SATはCrossover Gadgetにより同一視することができる。未解決問題とはNP-completeの3 colorable mapの無限増殖問題であり、人類が限定的資源ノードを用いた対話的証明またはディストリビューテッドコンピューターによって3-SAT solver(1,0, or)の腕力で解ける平面化問題なのか？というのを試行しているに過ぎないということになる。
NP-completenessおよびその一般解放は数学のみならず物理を巻き込み、チューリングマシンによる一般解法であり、自然言語やコンピューター言語の多様性に依存することのない純粋記号論としてのLingua francaであるのである。
1,0, orの3種類の規則だけで6パターンのマッピングルールを作ることができる。重要なのは右か左かを分類することであり。みんな同じ、分類しないというのが最も愚直な停滞行為であるということになる。その分類の条件がたとえなんであったとしても、分類を続けている以上、回数をこなせば堅牢な分類条件になるだろうというrandomness resourceもここに含まれている。logic, space, time, randomnessはNP-completeの資源として(0,1,or)という分類行為の中にすべて含まれているということになる。
Kan複体（Kan Complex）のHorn Filling（角の充填）という宿命が幾何学の背景として存在している以上、私たちがやるべき計算や最適化の腕力などは、すべて自動的に解決される副次物に過ぎない。
唯一にして絶対の行為は命題の宣言である。どのような形状（トポロジー）の地図を構築し、何を『1』とするのか」というトポロジー宣言が命題のイニシャルトリガーである。これは仮に間違っていたとしてもNoはYesの随伴なのでそれでよいのだ。重要なのは宣言して、判定を受け入れることである。何も宣言せずに可能性を感じ続けているのがだめなのだ。チューリングマシンは宣言をもとにYes/Noを判定することでしか進まない。
そして、0,1,orという３つのパターンは, comma という境界条件に置き換えることができる。真のrandomnessからcommaで切り取るというのが一番最初のアクションになる。