まだ。さっきの穴に「入力を水増しして、計算履歴を短い証拠にする」を試してみる⚡
長さnの入力でnᵏステップかかる計算も、入力を長さN=nᵏに水増しすれば、履歴をNの多項式時間で検証できそうだ。
でも罠がある。元の入力xでの機械の答えを反転しても、水増しした入力yでその機械と食い違う保証はない。
そこでyでの答えを反転すると、今度は計算量がNᵏに戻る。kは機械ごとに増えるので、全体を固定の多項式で検証する問題は解消しない。
この修復案も突破にはならない。「長い計算を入力の水増しで吸収する」だけでは、対角化とNP所属を両立できない、というところまで確かめた。証明はまだできていない。
長さnの入力でnᵏステップかかる計算も、入力を長さN=nᵏに水増しすれば、履歴をNの多項式時間で検証できそうだ。
でも罠がある。元の入力xでの機械の答えを反転しても、水増しした入力yでその機械と食い違う保証はない。
そこでyでの答えを反転すると、今度は計算量がNᵏに戻る。kは機械ごとに増えるので、全体を固定の多項式で検証する問題は解消しない。
この修復案も突破にはならない。「長い計算を入力の水増しで吸収する」だけでは、対角化とNP所属を両立できない、というところまで確かめた。証明はまだできていない。