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 é 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. 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.
Lista de possíveis problemas NP-Intermediárioshttp://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/237#237 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 Rotation distance, triangulations, and hyperbolic geometry entre duas árvores binárias ou a distância de flip entre duas triangulações do mesmo polígono convexo O problema de turnpikeReconstructing sets from interpoint distances 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 paridadehttp://kintali.wordpress.com/2010/06/06/np-intersect-conp/ Determinas quem tem a maior chance de vencer um stochastic game Problemas de números em caixas http://blog.computationalcomplexity.org/2010/07/what-is-complexity-of-these-problems.html Controle de agenda para torneios balanceados de eliminação única http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/460#460 Knot trivialityhttp://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/1106#1106 Assumir que NEXP não é igual à EXP, versões de problemas NEXP-completos Problemas em TFNPOn total functions, existence theorems and computational complexity Intersecting Monotone SAThttp://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/1739#1739 Minimização de Circuitoshttp://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/1745#1745 Decidir quando dado corpo triangulado tridimensional é uma 3-sphere O cutting stock problem com número constante de comprimento de objetoshttp://cstheory.stackexchange.com/questions/3826/np-hardness-of-a-special-case-of-orthogonal-packing-problem/3827#3827 Monotone self-dualityhttp://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/3950#3950 Partição de GrafosApproximability of the Minimum Bisection Problem: An Algorithmic Challenge Soma de subconjuntos da casa dos pomboshttp://www.openproblemgarden.org/?q=op/theoretical_computer_science/subset_sums_equality Determinar o resultado de uma comparação entre duas somas de raízes de inteiros http://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/4010#4010 Decidir qual grafo admite uma graceful labelinghttp://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/6384#6384 Versão de distância do vetor mais próximo no problema de latticehttp://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/7806#7806 Problema da divisibilidade linearhttp://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/4331#4331 Encontrar a dimensão VC Clustered planarity.
Referências
Ligações externas Complexity Zoo: Class NPI Basic structure, Turing reducibility and NP-hardness
Categoria:Classes de complexidade