Consequências de #P = FP

26

Quais seriam as consequências de #P = FP?

Estou interessado em conseqüências práticas e teóricas.

Do ponto de vista prático, estou particularmente interessado em consequências na inteligência artificial.

Ponteiros para papéis ou livros são mais que bem-vindos.

Por favor, não diga que #P = FP implica P = NP, eu já sei disso. Além disso, não diga "não haverá consequências práticas se o algoritmo for executado no tempo , onde é o número de elétrons no Universo"Ω(nα)α : permita-me supor que, se existe um algoritmo de tempo polinomial determinístico para um problema # P-complete, seu tempo de execução será "clement" ( , por exemplo).O(n2)

cc.complexity-theory ds.algorithms complexity-classes counting-complexity ai.artificial-intel Giorgio Camerani
fonte

Respostas:

25

Aqui estão algumas consequências teóricas da igualdade FP = # P, embora elas não tenham nada a ver com inteligência artificial. A suposição FP = # P é equivalente a P = PP , então deixe-me usar a última notação.

Se P = PP, então temos P = BQP : o cálculo do tempo polinomial quântico pode ser simulado pelo cálculo do tempo polinomial determinístico clássico. Isso é uma conseqüência direta do BQP⊆PP [ADH97, FR98] (e de um resultado anterior BQP⊆P PP [BV97]). Além do meu conhecimento, P = BQP não é conhecido por seguir a suposição P = NP. Essa situação é diferente do caso da computação aleatória ( BPP ): desde BPP⊆NP NP [Lau83], a igualdade P = BPP segue de P = NP.

Outra consequência de P = PP é que o modelo de computação de Blum-Shub-Smale sobre os reais com constantes racionais é equivalente às máquinas de Turing em certo sentido. Mais precisamente, P = PP implica P = BP (P ℝ 0 ); isto é, se um idioma L ⊆ {0,1} * é decidível por um programa sem constante sobre os reais em tempo polinomial, então L é decidido por uma máquina de Turing em tempo polinomial. (Aqui "BP" significa "Parte booleana" e não tem nada a ver com BPP.) Isso segue de BP (P ℝ 0 ) ⊆ CH [ABKM09]. Veja o documento para definições. Um problema importante na BP (P ℝ 0 ) é o problema da soma da raiz quadradae amigos (por exemplo: "Dado um número inteiro k e um conjunto finito de pontos de coordenadas inteiras no plano, existe uma árvore de extensão de comprimento total no máximo k ?") [Tiw92].

Da mesma forma para o segundo argumento, o problema do cálculo de um bit específico em x y quando inteiros positivos x e y são dadas em binário será em P se P = PP.

Referências

[ABKM09] Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen e Peter Bro Miltersen. Sobre a complexidade da análise numérica. SIAM Journal on Computing , 38 (5): 1987–2006, janeiro de 2009. http://dx.doi.org/10.1137/070697926

[ADH97] Leonard M. Adleman, Jonathan DeMarrais e Ming-Deh A. Huang. Computabilidade quântica. SIAM Journal on Computing , 26 (5): 1524-1540, outubro de 1997. http://dx.doi.org/10.1137/S0097539795293639

[BV97] Ethan Bernstein e Umesh Vazirani. Teoria da complexidade quântica. SIAM Journal on Computing , 26 (5): 1411-1473, outubro de 1997. http://dx.doi.org/10.1137/S0097539796300921

[FR98] Lance Fortnow e John Rogers. Limitações de complexidade na computação quântica. Journal of Computer and System Sciences , 59 (2): 240–252, outubro de 1999. http://dx.doi.org/10.1006/jcss.1999.1651

[Lau83] Clemens Lautemann. BPP e a hierarquia de tempo polinomial. Information Processing Letters , 17 (4): 215-217, novembro de 1983. http://dx.doi.org/10.1016/0020-0190(83)90044-3

[Tiw92] Prasoon Tiwari. Um problema que é mais fácil de resolver na RAM algébrica de custo unitário. Journal of Complexity , 8 (4): 393–397, dezembro de 1992. http://dx.doi.org/10.1016/0885-064X(92)90003-T

Tsuyoshi Ito
fonte
4
Você me venceu! Na verdade, você está certo sobre BQP vs NP. Parece haver evidências razoáveis ​​de que o BQP não está contido no PH (veja, por exemplo, arxiv.org/abs/0910.4698 ), embora eu acredite que a conjectura linial-nisana generalizada usada no segundo bit tenha sido mostrada desde então incorreta.
Joe Fitzsimons
9
@Turkistany: Se não me engano, P = NP implica P = BPP porque o BPP está contido no PH, e se P = NP, então P = PH.
Niel de Beaudrap
1
Aliás: +1 para (FP = # P) ⇔ (P = PP), deixando de lado o restante do conteúdo da resposta.
Niel de Beaudrap
2
@ Joe: À luz das respostas da outra pergunta, acho que a melhor evidência de “P = NP não implica P = BQP” sem provar realmente que P = NP ≠ BQP provavelmente seria um resultado de separação do oráculo: “Existe um oráculo A tal que P ^ A = NP ^ A ≠ BQP ^ A. ”É claro que isso não é nada fácil, porque esse resultado implicaria BQP ^ A⊈PH ^ A, resolvendo uma grande questão em aberto.
Tsuyoshi Ito 10/10
2
@Tsuyoshi: Você não pode construir tal oráculo a partir de qualquer oráculo em relação ao qual o BQP não esteja contido no PH, simplesmente juntando-o ao PH para formar um novo oráculo?
Joe Fitzsimons 10/10
15

Nos modelos gráficos , muitos dos problemas de estimativa são # P-completos, porque envolvem cálculos da soma do produto à la permanentes sobre gráficos gerais. Se #P = FP, os modelos gráficos de repente ficam muito mais fáceis, e não precisamos mais mexer nos modelos de baixa largura de árvore.

Suresh Venkat
fonte
5

PH⊆P#P♯P=FPPH

Mohammad Al-Turkistany
fonte
4
Alguém pode esclarecer: isso não é o mesmo que dizer "P = PH" (que se seguiria imediatamente de P = NP)?
Niel de Beaudrap
1
@Niel: Não é o mesmo, é mais forte.
Giorgio Camerani
2
PFP=P#P=FPPH⊆P#P=PFP=P⊆PH
1
@All: apenas para esclarecer --- meu primeiro comentário acima foi a seguinte pergunta "A resposta do turquia é equivalente à afirmação de que FP = # P implica P = PH?" Se eu quisesse saber se FP = # P era equivalente a P = PH, eu teria perguntado isso em um comentário no post original, não na resposta do turquistão.
Niel de Beaudrap 8/10
1
@Niel: Você está certo. É o mesmo que dizer P = PH, que segue de P = NP. Portanto, o uso do teorema de Toda não foi necessário, pois FP = #P já implica P = NP = PH.
precisa