P= NP in Automata cellulare di spazi iperbolici?

Question

Ho letto alcuni anni fa in Questo libro questo I problemi NP sono trattabili nello spazio degli automi cellulari nel piano iperbolico . Cosa significa questo? P = NP secondo questi libri / documenti?

Alcuni estratti dalla carta:

.

È noto che se abbiamo alberi binari a nostra disposizione "GRATIS", è possibile risolvere i problemi NP in tempo polinomiale, vedere [14, 5]. Tuttavia, non è immediato implementare algoritmi alberali binari nel PentaGrid e l'obiettivo di questa sezione è quello di indicare come si può procedere.

Dalla mia comprensione, il P= NP Il problema è alla ricerca di algoritmi polinomiali a risolvere problemi complicati. Dalla mia occhiata curiosa attraverso i libri e i documenti, sembra suggerire di aver risolto il problema. Cosa mi manca?

qui è un altro documento, intitolato in alcuni spazi curvi, noi Può risolvere i problemi di NP-Hard in tempo polinomiale: verso il sogno di Matiyasevich .

Answer 1

Il problema P / vs. NP è una domanda su Turing Machines $ T $ , poiché le classi di complessità P e NP sono definite in termini di queste macchine teoriche. Chiamiamo queste classi $ p_t $ e $ np_t $ da ora in poi. La carta introduce una nuova macchina di calcolo teorica $ h $ che ha classi associate $ p_h $ (corre in polinomiale Tempo sull'automato cellulare iperbolico) e $ NP_H $ (funziona in tempo polinomiale non deterministico sull'automato cellulare iperbolico).

Il primo passo in questo documento è una prova che il problema 3Sat, una ben nota $ NP_T $ - Problema di complotto, può essere risolto in tempo polinomiale su questa macchina , cioè questo problema si trova in $ p_h $ . Successivamente, mostrano qualsiasi riduzione del tempo polinomiale su una macchina di Turing può essere eseguita in tempo polinomiale sul loro automa iperbolico. Dal momento che 3SAT è $ np_t $ -complete, qualsiasi classe $ np_t $ istanza può essere ridotto a un'istanza 3SAT in Tempo polinomiale (su $ T $ per definizione, così anche su $ h $ dal loro lemma) e poi essere risolto risolvendo 3sat in Poly-Time, sia su Automaton Hyperbol. In altre parole, il risultato principale di questo documento (teorema 1) può essere scritto come $ NP_T \ SOTETETQ P_H $ nella nostra notazione. Questo non fornisce una soluzione al problema P vs. NP, perché ciò avrebbe bisogno di mettere in relazione le classi $ np_t $ e $ P_t $ .

Si noti che gli autori includono alcune osservazioni sul problema P VS. NP nella sezione 4.2, dove affermano il loro risultato sono prove per P $ \ NEQ $ NP ( !):

.

una terza direzione è costituita dalla nuova luce che ha perso la domanda P= NP nel Impostazioni ordinarie. Poiché lo spazio iperbolico ha proprietà che sono molto diverse dalle proprietà dello spazio euclideo, in particolare, ha molte altre direzioni, non sarebbe un suggerimento favorevole per dimostrare che p $ \ neq $ NP in condizioni euclidee? Sembra che Negli ultimi dieci anni le opere nel campo della complessità inclinare le persone a credere Più in P $ \ neq $ np. Apparentemente, il risultato attuale appartiene anche a quella tendenza.