Wikipédia

NP-Intermediário

Em complexidade computacional, problemas que são da classe de complexidadeNP mas não não estão contido na classe P nem na classe NP-Completo são chamados NP-Intermediários, e a classe de tais problemas é chamada de NPI. O teorema de Ladner, mostrado em 1975 por Richard Ladner[1] é um resultado assertivo de que, se P ≠ NP, então NPI não é vazio; ou seja, NP contém problemas que não estão contidos em P nem NP-completo. Uma vez que a outra direção é trivial, nós podemos dizer que P = NP  se, e somente se NPI é vazio.

Assumindo que P ≠ NP, Ladner explicitamente construiu um problema em NPI, apesar do problema ser artificial e de qualquer outra forma, desinteressante. Ainda é um questionamento em aberto se qualquer problema "natural" possui a mesma propriedade: o Teorema da Dicotomia de Schaefer provê condições sobre as quais classes de problemas restritos de satisfatibilidade booleana não podem estar presentes em NPI.[2] Alguns problemas que são considerados bons candidados à pertinência aos NP-Intermediários são oproblema do isomorfismo de grafo, fatoração, e a computação do logaritmo discreto.[3]

Lista de possíveis problemas NP-Intermediários[4]

editar
  • Fatoração de inteiros
  • Problemas de Isomorfismo: problema de isomorfismo de grafo, problema de isomorfismo de grupo, automorfismo de grupo, isomorfismo de anéis, automorfismo de anéis
  • Computar distância de rotação [5] entre duas árvores binárias ou a distância de flip entre duas triangulações do mesmo polígono convexo
  • O problema de turnpike[6] de reconstrução de pontos em linha pela sua distância multiset
  • Logaritmo Discreto e outros problemas e desafios criptográficos
  • Determinar vencedor em jogos de paridade[7]
  • Determinas quem tem a maior chance de vencer um stochastic game[7]
  • Problemas de números em caixas [8]
  • Controle de agenda para torneios balanceados de eliminação única [9]
  • Knot triviality[10]
  • Assumir que NEXP não é igual à EXP, versões de problemas NEXP-completos
  • Problemas em TFNP[11]
  • Intersecting Monotone SAT[12]
  • Minimização de Circuitos[13][14]
  • Decidir quando dado corpo triangulado tridimensional é uma 3-sphere
  • O cutting stock problem com número constante de comprimento de objetos[15]
  • Monotone self-duality[16]
  • Partição de Grafos[17]
  • Soma de subconjuntos da casa dos pombos[18]
  • Determinar o resultado de uma comparação entre duas somas de raízes de inteiros [19]
  • Decidir qual grafo admite uma graceful labeling[20]
  • Versão de distância do vetor mais próximo no problema de lattice[21]
  • Problema da divisibilidade linear[22]
  • Encontrar a dimensão VC[23]
  • Clustered planarity[24]

Referências

editar
  1. ↑ Ladner, Richard (1975). «On the Structure of Polynomial Time Reducibility». Journal of the ACM (JACM). 22 (1): 155–171. doi:10.1145/321864.321877 
  2. ↑ Grädel, Erich; Kolaitis, Phokion G.; Libkin, Leonid; Marx, Maarten; Spencer, Joel; Vardi, Moshe Y.; Venema, Yde; Weinstein, Scott (2007). Finite model theory and its applications. Col: Texts in Theoretical Computer Science. An EATCS Series. Berlin: Springer-Verlag. p. 348. ISBN 978-3-540-00428-8. Zbl 1133.03001 
  3. ↑ «Problems Between P and NPC». Theoretical Computer Science Stack Exchange. 20 de agosto de 2011. Consultado em 1 de novembro de 2013 
  4. ↑ http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/237#237
  5. ↑ Rotation distance, triangulations, and hyperbolic geometry
  6. ↑ Reconstructing sets from interpoint distances
  7. ↑ a b http://kintali.wordpress.com/2010/06/06/np-intersect-conp/
  8. ↑ http://blog.computationalcomplexity.org/2010/07/what-is-complexity-of-these-problems.html
  9. ↑ http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/460#460
  10. ↑ http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/1106#1106
  11. ↑ On total functions, existence theorems and computational complexity
  12. ↑ http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/1739#1739
  13. ↑ http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/1745#1745
  14. ↑ Kabanets, Valentine; Cai, Jin-Yi (2000), «Circuit minimization problem», Proc. 32nd Symposium on Theory of Computing, Portland, Oregon, USA, pp. 73–79, doi:10.1145/335305.335314, Predefinição:ECCC 
  15. ↑ http://cstheory.stackexchange.com/questions/3826/np-hardness-of-a-special-case-of-orthogonal-packing-problem/3827#3827
  16. ↑ http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/3950#3950
  17. ↑ Approximability of the Minimum Bisection Problem: An Algorithmic Challenge
  18. ↑ http://www.openproblemgarden.org/?q=op/theoretical_computer_science/subset_sums_equality
  19. ↑ http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/4010#4010
  20. ↑ http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/6384#6384
  21. ↑ http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/7806#7806
  22. ↑ http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/4331#4331
  23. ↑ Papadimitriou, Christos H.; Yannakakis, Mihalis (1996), «On limited nondeterminism and the complexity of the V-C dimension», Journal of Computer and System Sciences, 53 (2, part 1): 161–170, MR 1418886, doi:10.1006/jcss.1996.0058 
  24. ↑ Cortese, Pier Francesco; Di Battista, Giuseppe; Frati, Fabrizio; Patrignani, Maurizio; Pizzonia, Maurizio (2008), «C-planarity of C-connected clustered graphs», Journal of Graph Algorithms and Applications, 12 (2): 225–262, MR 2448402, doi:10.7155/jgaa.00165 .

Ligações externas

editar
Obtida de "https://pt.wikipedia.org/w/index.php?title=NP-Intermediário&oldid=67430137"