3
$\begingroup$

I read a few years ago in this book that NP problems are tractable in the space of cellular automata in the hyperbolic plane. What does this mean? Does P = NP according to these books/papers?

Some excerpts from the paper:

It is well known that if we have binary trees at our disposal “for free”, it is possible to solve NP-problems in polynomial time, see [14, 5]. However, it is not immediate to implement binary tree algorithms in the pentagrid, and the goal of this section is to indicate how one can proceed.

From my understanding, the P = NP problem is looking for polynomial-time algorithms to solve complicated problems. From my cursory glance through the books and papers, it seems to suggest that he has solved the problem. What am I missing?

Here is another paper, titled In Some Curved Spaces, We Can Solve NP-Hard Problems in Polynomial Time: Towards Matiyasevich's Dream.

$\endgroup$

1 Answer 1

7
$\begingroup$

The P vs. NP problem is a question about Turing machines $T$, because the complexity classes P and NP are defined in terms of these theoretical machines. Let's call these classes $P_T$ and $NP_T$ from now on. The paper introduces a new theoretical computation machine $H$ that has associated classes $P_H$ (runs in polynomial time on the hyperbolic cellular automaton) and $NP_H$ (runs in non-deterministic polynomial time on the hyperbolic cellular automaton).

The first step in this paper is a proof that the 3SAT problem, a well known $NP_T$-complete problem, can be solved in polynomial time on this machine, i.e. this problem lies in $P_H$. Next, they show any polynomial time reduction on a Turing machine can be performed in polynomial time on their hyperbolic automaton. Since 3SAT is $NP_T$-complete, any $NP_T$ instance can be reduced to a 3SAT instance in polynomial time (on $T$ by definition, so also on $H$ by their lemma) and then be solved by solving 3SAT in poly-time, both on the hyperbolic automaton. In other words, the main result of this paper (Theorem 1) can be written as $NP_T \subseteq P_H$ in our notation. This does not give a solution to the P vs. NP problem, because that would need to relate the classes $NP_T$ and $P_T$.

Note that the authors include some remarks on the P vs. NP problem in section 4.2, where they claim their result is evidence for P$\neq$NP (!):

A third direction consists of the new light shed on the P=NP question in the ordinary settings. As the hyperbolic space has properties which are very different from the properties of the euclidean space, in particular, it has many more directions, would not that be a hint favorable to prove that P$\neq$NP in euclidean conditions? It seems that for the last ten years the works in the field of complexity incline people to believe more in P$\neq$NP. Apparently, the present result also belongs to that trend.

$\endgroup$
4
  • 1
    $\begingroup$ Is this at all exciting, or has this been broadly known for decades? Haha. $\endgroup$ Commented Aug 18, 2020 at 8:48
  • $\begingroup$ @LancePollard What has been known, exactly? That there are "reasonable" computational models $X$ for which $NP_T\subseteq P_X$? In the quote in your question, it is claimed that reference [14] gives an example of that, which is from 1986. $\endgroup$
    – Discrete lizard
    Commented Aug 18, 2020 at 9:15
  • $\begingroup$ I guess I just remember hearing some hyperbole around P = NP and so saw this paper and thought maybe they did something about it and no one noticed. I've seen other papers that went ignored. $\endgroup$ Commented Aug 18, 2020 at 10:49
  • $\begingroup$ For reference this is where I was coming from: "Theorem 1 (Margenstern–Morita). NP-problems can be solved in polynomial time in the space of cellular automata in the hyperbolic plane." from here. $\endgroup$ Commented Jun 17, 2021 at 3:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.