P = NP negli automi cellulari degli spazi iperbolici?
Ho letto qualche anno fa in questo libro che i problemi NP sono trattabili nello spazio degli automi cellulari nel piano iperbolico . Cosa significa questo? P = NPSecondo questi libri/documenti ?
Alcuni estratti dal giornale:
È ben noto che se abbiamo alberi binari a nostra disposizione “gratis”, è possibile risolvere problemi NP in tempo polinomiale, vedi [14, 5]. Tuttavia, non è immediato implementare algoritmi ad albero binario nella pentagriglia e l'obiettivo di questa sezione è indicare come si può procedere.
Da quanto ho capito, il problema P = NP è alla ricerca di algoritmi in tempo polinomiale per risolvere problemi complicati. Dalla mia rapida occhiata ai libri e alle carte, sembra suggerire che abbia risolto il problema. Cosa mi manca?
Ecco un altro documento, intitolato In Some Curved Spaces, We Can Solve NP-Hard Problems in Polynomial Time: Towards Matiyasevich's Dream .
Risposte
Il problema P vs. NP è una domanda sulle macchine di Turing$T$, perché 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. Il documento introduce una nuova macchina di calcolo teorica$H$che ha classi associate$P_H$(corre in tempo polinomiale sull'automa cellulare iperbolico) e$NP_H$(corre in tempo polinomiale non deterministico sull'automa cellulare iperbolico).
Il primo passo in questo documento è una prova che il problema 3SAT, ben noto$NP_T$-problema completo, può essere risolto in tempo polinomiale su questa macchina, cioè questo problema si trova in$P_H$. Successivamente, mostrano che qualsiasi riduzione del tempo polinomiale su una macchina di Turing può essere eseguita in tempo polinomiale sul loro automa iperbolico. Poiché 3SAT è$NP_T$-completo, qualsiasi$NP_T$può essere ridotta a un'istanza 3SAT in tempo polinomiale (on$T$per definizione, così via$H$dal loro lemma) e poi essere risolti risolvendo 3SAT in poly-time, entrambi sull'automa iperbolico. In altre parole, il risultato principale di questo articolo (Teorema 1) può essere scritto come$NP_T \subseteq P_H$nella nostra notazione. Questo non fornisce una soluzione al problema P vs. NP, perché ciò dovrebbe 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 che il loro risultato è una prova per P$\neq$PN (!):
Una terza direzione è costituita dalla nuova luce gettata sulla questione P=NP nei contesti ordinari. Poiché lo spazio iperbolico ha proprietà molto diverse da quelle dello spazio euclideo, in particolare ha molte più direzioni, non sarebbe questo un indizio favorevole per dimostrare che P$\neq$NP in condizioni euclidee? Sembra che negli ultimi dieci anni i lavori nel campo della complessità spingano le persone a credere di più in P$\neq$N.P. Apparentemente, anche il presente risultato appartiene a tale tendenza.