p= np在双曲空间的蜂窝自动机中吗？

Question

我在本书那是 NP问题在双曲线平面中的蜂窝自动机空间中是易行的。这是什么意思？根据这些书籍/论文是否是生成的？

一些摘录纸质：

众所周知，如果我们在我们的处置“免费”，则可以解决多项式时间中的NP问题，见[14,5]。但是，在Pentagrid中实现二叉树算法并不立即实现，并且本节的目标是指示如何继续进行。

从我的理解中， p= np 问题正在寻找多项式时间算法解决复杂的问题。从我的练习术一瞥通过书籍和论文，似乎表明他已经解决了这个问题。我错过了什么？

这里是另一篇论文，在一些弯曲的空间中，我们可以解决多项式时间的NP难题：走向Matiyasevich的梦想

Answer 1

p vs.np问题是关于图灵机 $ t $ 的问题，因为复杂性类p和np是根据这些理论机器定义的。让我们调用这些类 $ p_t $ 和 $ np_t $ 从现在开启。本文介绍了一个新的理论计算机 $ h $ ，它具有关联的类 $ p_h $ （在多项式中运行在双曲线蜂窝自动机上的时间）和<跨度类=“数学容器”> $ NP_H $ （在双曲线蜂窝自动机上的非确定性多项式时间运行）。

本文的第一步是一个证明，3SAT问题，一个众所周知的 $ np_t $ -complete问题，可以在这台机器上的多项式时间中解决，即此问题位于 $ p_h $ 中。接下来，它们表明可以在双曲线自动机上的多项式时间中进行图定机器的任何多项式时间。由于3SAT是 $ np_t $ -complete，任何 $ np_t $ 实例可以减少到3SAT实例多项式时间（在 $ t $ 根据定义，也on $ h $ 按其引理）然后通过在双曲线自动机上求解3SAT来解决3SAT。换句话说，本文（定理1）的主要结果可以写作 $ np_t \ subseteq p_h $ 在我们的符号中。这不会给出P与NP问题的解决方案，因为它需要将类 $ np_t $ 和相关联$ p_t $ 。

请注意，作者在第4.2节中包含关于P与NP问题的一些评论，其中他们声称它们的结果是P $ \ neq $ np（ ！）：

第三个方向包括在p= np问题上的新光线 普通设置。由于双曲线空间具有与欧几里德空间的性质非常不同的属性，特别是它具有更多方向，这不会是一个有利于证明p $ \的提示Neq $ np在欧几里德的条件下？看起来 在过去的十年中，复杂性领域的作品倾向于人们相信 更多在p $ \ neq $ np。显然，目前的结果也属于这种趋势。