Hiperbolik Uzayların Hücresel Otomatında P = NP mi?

Question

Birkaç yıl önce bu kitapta NP problemlerinin hiperbolik düzlemdeki hücresel otomata uzayında izlenebilir olduğunu okudum . Ne anlama geliyor? Does P = NPbu kitaplar / belgelere göre?

Gazeteden bazı alıntılar:

Elimizde "ücretsiz" ikili ağaçlar varsa, NP problemlerini polinom zamanda çözmenin mümkün olduğu iyi bilinmektedir, bkz. [14, 5]. Bununla birlikte, ikili ağaç algoritmalarını pentagridde hemen uygulamak mümkün değildir ve bu bölümün amacı, bir kişinin nasıl ilerleyebileceğini göstermektir.

Anladığım kadarıyla, P = NP problemi, karmaşık problemleri çözmek için polinom-zaman algoritmaları arıyor. Kitaplara ve makalelere üstünkörü bakışımdan, sorunu çözdüğünü gösteriyor gibi görünüyor. Neyi kaçırıyorum?

İşte Bazı Eğri Uzaylarda, Polinom Zamanında NP-Zor Problemleri Çözebiliriz: Matiyasevich'in Rüyasına Doğru başlıklı başka bir makale .

Answer 1

P - NP problemi, Turing makineleri ile ilgili bir sorudur $T$çünkü karmaşıklık sınıfları P ve NP bu teorik makineler açısından tanımlanmıştır. Bu sınıfları arayalım$P_T$ ve $NP_T$bundan sonra. Makale, yeni bir teorik hesaplama makinesini tanıtıyor$H$ ilişkili sınıfları olan $P_H$ (hiperbolik hücresel otomatta polinom zamanda çalışır) ve $NP_H$ (hiperbolik hücresel otomatta deterministik olmayan polinom zamanında çalışır).

Bu makaledeki ilk adım, iyi bilinen 3SAT sorununun bir kanıtıdır. $NP_T$-tamamlı problem, bu makinede polinom zamanda çözülebilir, yani bu problem $P_H$. Daha sonra, bir Turing makinesinde herhangi bir polinom zaman azaltmasının, hiperbolik otomatlarında polinom zamanında gerçekleştirilebileceğini gösterirler. 3SAT,$NP_T$-komple, herhangi biri $NP_T$ örnek, polinom zamanda bir 3SAT örneğine indirgenebilir (açık $T$ tanım gereği, aynı zamanda $H$lemma ile) ve sonra 3SAT'ı çoklu zamanda çözerek çözülür, her ikisi de hiperbolik otomatta. Başka bir deyişle, bu makalenin ana sonucu (Teorem 1) şu şekilde yazılabilir:$NP_T \subseteq P_H$bizim gösterimde. Bu, P-NP problemine bir çözüm vermez, çünkü bunun sınıfları ilişkilendirmesi gerekir.$NP_T$ ve $P_T$.

Yazarların, sonuçlarının P için kanıt olduğunu iddia ettikleri bölüm 4.2'de P-NP problemi hakkında bazı açıklamalar eklediklerini unutmayın.$\neq$NP (!):

Üçüncü bir yön, sıradan ortamlarda P = NP sorusu üzerine yeni ışık dökülmesinden oluşur. Hiperbolik uzay, öklid uzayının özelliklerinden çok farklı özelliklere sahip olduğundan, özellikle çok daha fazla yöne sahip olduğundan, P$\neq$Öklid koşullarında NP? Görünüşe göre son on yıldır karmaşıklık alanındaki çalışmalar insanları P$\neq$NP. Görünüşe göre, mevcut sonuç da bu eğilime ait.