Técnicas para mostrar que o problema está na dureza "limbo"

Dado um novo problema em cuja verdadeira complexidade está em algum lugar entre e sendo NP-complete, existem dois métodos que eu conheço que podem ser usados ​​para provar que resolver isso é difícil:$\mathsf{NP}$$\mathsf{P}$

1. Mostre que o problema é GI-completo (GI = Isomorfismo do gráfico)
2. Mostre que o problema está em . Pelos resultados conhecidos, esse resultado implica que, se o problema for NP-completo, o PH entrará em colapso para o segundo nível. Por exemplo, o famoso protocolo para Nonisomorphism Graph faz exatamente isso.$\mathsf{co-AM}$

Existem outros métodos (talvez com diferentes "pontos fortes da crença") que foram usados? Para qualquer resposta, é necessário um exemplo de onde ele realmente foi usado: obviamente existem muitas maneiras de tentar mostrar isso, mas os exemplos tornam o argumento mais convincente.

Mostrar que seu problema está no coAM (ou SZK) é realmente uma das principais maneiras de gerar evidências para o "limbo da dureza". Mas além disso, existem vários outros:

• Mostre que seu problema está no NP ∩ coNP. (Exemplo: Factoring.)
• Mostre que seu problema é solucionável em tempo quase-polinomial. (Exemplos: dimensão VC, aproximando jogos gratuitos.)
• Mostre que seu problema não é mais difícil do que inverter funções unidirecionais ou resolver o NP em média. (Exemplos: muitos problemas em criptografia.)
• Mostre que o seu problema se reduz a (por exemplo) Jogos exclusivos ou Expansão em conjuntos pequenos.
• Mostre que seu problema está no BQP. (Exemplo: fatoração, embora é claro que também esteja no NP ∩ coNP.)
• Descartar grandes classes de reduções de completude de NP. (Exemplo: O Problema de Minimização de Circuitos, estudado por Kabanets e Cai.)

Tenho certeza de que há outras que estou esquecendo.

Pelo comentário acima: se um problema parecer difícil o suficiente, mas você não conseguir provar que é NP-completo, uma verificação rápida é para contar o número de cadeias de comprimento no idioma: se o conjunto for escasso, é improvável que seja NPC, caso contrário P = NP pelo teorema de Mahaney ... então é melhor direcionar esforços para provar que ele está em P :-) :-)$n$

Um exemplo é o problema de particionar números em k-boxes (do blog da Fortnow & Gasarch, fonte original: Cyberpuzzles do Doctor Ecco ):

{ 1 , . . . , n }  em no máximo k caixas para que nenhuma caixa tenha  x , y , z  com  x + y = z $\{ (n,k) \mid \text{ there exists a way to partition }$ $\{1,...,n\} \text{ into at most k boxes so that no box has } x,y,z \text{ with } x+y=z \}$

Aqui estão três adições à lista de Scott:

• Mostre que seu problema está em alguns pontos. Isso significa que o número de soluções é limitado por algum polinômio. (Exemplo: problema do turnpike). Sabe-se que nenhum problema de NP-completo está em poucosP. (impossível a menos que P = NP).
• $LOGNP$$NP[log^2n]$
• $2^{n^{\epsilon}}$$NP$$\epsilon \gt 0$$n\ge 0$$2^{n^{\epsilon}}$$n$

$coNP ⊆ NP/poly$