Konsekwencje #P = FP

Jakie byłyby konsekwencje #P = FP?

Interesują mnie zarówno praktyczne, jak i teoretyczne konsekwencje.

Z praktycznego punktu widzenia szczególnie interesują mnie konsekwencje dla sztucznej inteligencji.

Wskaźniki do dokumentów lub książek są mile widziane.

Nie mów, że #P = FP oznacza P = NP, już to wiem. Nie mów też: „nie będzie żadnych praktycznych konsekwencji, jeśli algorytm będzie działał w czasie , gdzie jest liczbą elektronów we Wszechświecie” $\Omega(n^{\alpha})$ $\alpha$ : pozwólcie mi założyć, że jeśli istnieje deterministyczny algorytm wielomianowy dla problemu # P-zupełnego, jego czas działania to „clement” (na przykład ). $O(n^2)$

cc.complexity-theory ds.algorithms complexity-classes counting-complexity ai.artificial-intel Giorgio Camerani
źródło

Odpowiedzi:

Oto kilka teoretycznych konsekwencji równości FP = # P, chociaż nie mają one nic wspólnego ze sztuczną inteligencją. Założenie FP = # P jest równoważne P = PP , więc pozwól mi użyć tej ostatniej notacji.

Jeśli P = PP, to mamy P = BQP : kwantowe obliczenia wielomianowe w czasie mogą być symulowane przez klasyczne, deterministyczne obliczenia wielomianowe w czasie. Jest to bezpośrednia konsekwencja BQP⊆PP [ADH97, FR98] (i wcześniejszego wyniku BQP⊆P ^PP [BV97]). Zgodnie z moją wiedzą, P = BQP nie jest znane z założenia P = NP. Ta sytuacja różni się od przypadku obliczeń losowych ( BPP ): ponieważ BPP⊆NP ^NP [Lau83], równość P = BPP wynika z P = NP.

Inną konsekwencją P = PP jest to, że model obliczeń Bluma-Shuba-Smale'a na liczbach rzeczywistych ze stałymi wymiernymi jest w pewnym sensie równoważny maszynom Turinga. Dokładniej, P = PP oznacza P = BP (P _ℝ⁰ ); to znaczy, jeśli język L ⊆ {0,1} ^* jest rozstrzygalny przez program niezmienny w czasie rzeczywistym w czasie wielomianowym, wówczas L jest rozstrzygalny przez maszynę Turinga w czasie wielomianowym. (Tutaj „BP” oznacza „część logiczną” i nie ma nic wspólnego z BPP.) Wynika to z BP (P _ℝ⁰ ) ⊆ CH [ABKM09]. Definicje znajdują się w dokumencie. Ważnym problemem w BP (P _ℝ⁰ ) jest problem z pierwiastkiem kwadratowymi przyjaciele (np. „Biorąc pod uwagę liczbę całkowitą k i skończony zestaw punktów współrzędnych całkowitych na płaszczyźnie, czy istnieje drzewo rozpinające o całkowitej długości co najwyżej k ?”) [Tiw92].

Podobnie jak w przypadku drugiego argumentu, problem obliczania określonego bitu w x ^y, gdy dodatnie liczby całkowite x i y podane są w postaci binarnej, będzie w P, jeśli P = PP.

Referencje

[ABKM09] Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen i Peter Bro Miltersen. O złożoności analizy numerycznej. SIAM Journal on Computing , 38 (5): 1987–2006, styczeń 2009. http://dx.doi.org/10.1137/070697926

[ADH97] Leonard M. Adleman, Jonathan DeMarrais i Ming-Deh A. Huang. Obliczalność kwantowa. SIAM Journal on Computing , 26 (5): 1524/40, październik 1997. http://dx.doi.org/10.1137/S0097539795293639

[BV97] Ethan Bernstein i Umesh Vazirani. Teoria złożoności kwantowej. SIAM Journal on Computing , 26 (5): 1411/73, październik 1997. http://dx.doi.org/10.1137/S0097539796300921

[FR98] Lance Fortnow i John Rogers. Ograniczenia złożoności obliczeń kwantowych. Journal of Computer Sciences i systemowe , 59 (2): 240-252, październik 1999. http://dx.doi.org/10.1006/jcss.1999.1651

[Lau83] Clemens Lautemann. BPP i wielomianowa hierarchia czasu. Information Processing Letters , 17 (4): 215–217, listopad 1983. http://dx.doi.org/10.1016/0020-0190(83)90044-3

[Tiw92] Prasoon Tiwari. Problem łatwiejszy do rozwiązania w algebraicznej pamięci RAM typu unit-cost. Journal of Complexity , 8 (4): 393–397, grudzień 1992. http://dx.doi.org/10.1016/0885-064X(92)90003-T

Tsuyoshi Ito
źródło

Pobiłeś mnie do tego! Właściwie masz rację co do BQP vs NP. Wydaje się, że istnieją uzasadnione dowody, że BQP nie jest zawarty w PH (patrz na przykład arxiv.org/abs/0910.4698 ), chociaż uważam, że Uogólniona hipoteza liniowa-Nisana, która jest używana w drugim bicie, okazała się odtąd niepoprawna.

Joe Fitzsimons,

@turkistany: Jeśli się nie mylę, P = NP oznacza P = BPP, ponieważ BPP jest zawarty w PH, a jeśli P = NP, to P = PH.

Niel de Beaudrap,

Nawiasem mówiąc: +1 za (FP = # P) ⇔ (P = PP), nawet odkładając na bok resztę odpowiedzi.

Niel de Beaudrap,

@Joe: W świetle odpowiedzi na inne pytanie, uważam, że najlepszy dowód „P = NP nie oznacza P = BQP” bez faktycznego udowodnienia P = NP ≠ BQP prawdopodobnie byłby wynikiem separacji wyroczni: „Istnieje wyrocznia A taka, że P ^ A = NP ^ A ≠ BQP ^ A. ”Oczywiście nie jest to wcale łatwe, ponieważ wynik ten oznaczałby BQP ^ A⊈PH ^ A, rozstrzygając duże otwarte pytanie.

Tsuyoshi Ito,

@Tsuyoshi: Czy nie możesz zbudować takiej wyroczni z jakiejkolwiek wyroczni, w stosunku do której BQP nie jest zawarte w PH, po prostu łącząc ją z PH w celu utworzenia nowej wyroczni?

Joe Fitzsimons,

W modelach graficznych wiele problemów z estymacją jest # P-kompletnych, ponieważ wiążą się one z wykonywaniem obliczeń sumy iloczynów stałych na ogólnych wykresach. Jeśli #P = FP, wtedy modele graficzne nagle stają się o wiele łatwiejsze i nie musimy już więcej grzebać w modelach o niskiej szerokości pleców.

Suresh Venkat
źródło

$PH \subseteq P^{\#P}$ $\sharp P=FP$ $PH$

Mohammad Al-Turkistany
źródło

Czy ktoś może wyjaśnić: czy to nie to samo, co powiedzenie „P = PH” (co natychmiast wynikałoby z P = NP)?

Niel de Beaudrap,

@Niel: To nie to samo, jest silniejsze.

Giorgio Camerani,

P^{FP} = P

$\text P^{\text{FP}} = \text P$

# P = FP

$\#\text P = \text{FP}$

PH \subseteq P^{# P} = P^{FP} = P \subseteq PH

$\text{PH} \subseteq \text P^{\#\text P} = \text P^{\text{FP}} = \text P \subseteq \text{PH}$

@Wszystko: tylko dla wyjaśnienia --- mój pierwszy powyższy komentarz zadawał następujące pytanie „Czy odpowiedź turkistany jest równoważna stwierdzeniu, że FP = # P oznacza P = PH?” Gdybym chciał wiedzieć, czy FP = # P jest równoważne P = PH, zapytałbym o to w komentarzu do oryginalnego postu, a nie w odpowiedzi turkistany.

Niel de Beaudrap,

@Niel: Masz rację. Jest to to samo, co powiedzenie P = PH, które wynika z P = NP. Dlatego użycie twierdzenia Tody nie było konieczne, ponieważ FP = #P już implikuje P = NP = PH.

Robin Kothari,