双曲空間のセルオートマトンでP = NPですか？
私は数年前にこの本で、NP問題は双曲平面のセルオートマトンの空間で扱いやすいことを読みました。これは何を意味するのでしょうか？P = NPこれらの本/論文によると？
論文からの抜粋：
「無料」で自由に使える二分木があれば、多項式時間でNP問題を解くことができることはよく知られています。[14,5]を参照してください。ただし、ペンタグリッドにバイナリツリーアルゴリズムを実装するのはすぐにはできません。このセクションの目的は、どのように進めることができるかを示すことです。
私の理解では、P = NP問題は、複雑な問題を解決するための多項式時間アルゴリズムを探しています。本や論文をざっと見ただけで、彼が問題を解決したことを示唆しているようです。何が足りないのですか？
これは、「いくつかの湾曲した空間で、多項式時間でNP困難な問題を解決できる：マチャセビッチの夢に向けて」というタイトルの別の論文です。
回答
P対NP問題はチューリングマシンに関する質問です $T$、複雑さクラスPとNPは、これらの理論上のマシンに関して定義されているためです。これらのクラスを呼びましょう$P_T$ そして $NP_T$今後。この論文は、新しい理論的計算機を紹介します$H$ 関連付けられたクラスがあります $P_H$ （双曲線セルオートマトンで多項式時間で実行されます）および $NP_H$ （双曲線セルオートマトンで非決定論的多項式時間で実行されます）。
この論文の最初のステップは、よく知られている3SAT問題の証明です。 $NP_T$-完全な問題、このマシンでは多項式時間で解決できます。つまり、この問題は $P_H$。次に、チューリングマシンでの多項式時間の短縮は、双曲線オートマトンで多項式時間で実行できることを示しています。3SATは$NP_T$-完了、任意 $NP_T$ インスタンスは、多項式時間で3SATインスタンスに減らすことができます（ $T$ 定義上、 $H$補題によって）そして、双曲線オートマトンの両方で、ポリタイムで3SATを解くことによって解決されます。言い換えれば、この論文の主な結果（定理1）は次のように書くことができます。$NP_T \subseteq P_H$私たちの表記法で。これは、クラスを関連付ける必要があるため、P対NP問題の解決策にはなりません。$NP_T$ そして $P_T$。
著者はセクション4.2にP対NP問題に関するいくつかの意見を含めていることに注意してください。そこでは彼らの結果はPの証拠であると主張しています。$\neq$NP（！）：
3番目の方向は、通常の設定でのP = NP質問に当てられる新しい光で構成されます。双曲空間はユークリッド空間の性質とは非常に異なる性質を持っているので、特にそれはより多くの方向を持っているので、それはPを証明するのに好ましいヒントではないでしょう。$\neq$ユークリッド条件のNP？過去10年間、複雑さの分野での作業により、人々はPをより信じるようになりました。$\neq$NP。どうやら、現在の結果もその傾向に属しています。