Existem problemas de "NP-Intermediário-Completo"?

Suponha P NP.$\ne$

O Teorema de Ladner diz que existem problemas NP Intermediários (problemas em NP que não estão nem em P nem em NP-Completo). Eu encontrei algumas referências veladas on-line que sugerem (eu acho) que existem muitos "níveis" de linguagens mutuamente redutíveis dentro do NPI que, definitivamente, nem todos se desintegram em um.

Eu tenho algumas perguntas sobre a estrutura desses níveis.

1. Existem problemas "NP-Intermediário-Completo" - ou seja, problemas NP-Intermediários, nos quais todos os outros problemas NP-Intermediários são reduzidos em tempos de polipose?
2. Classifique NP - P em classes de equivalência, onde redutibilidade mútua é a relação de equivalência. Agora imponha uma ordem a essas classes de equivalência: se os problemas em B se reduzirem a problemas em A (tão claramente a classe de equivalência NP-Complete é o elemento máximo). Essa é uma ordem total (ou seja, os problemas são organizados em uma cadeia descendente infinita)? Caso contrário, a "estrutura em árvore" da ordem parcial tem um fator de ramificação finito?$A > B$$B$$A$
3. Existem outros componentes estruturais conhecidos interessantes de NP - P? Existem questões abertas interessantes sobre a estrutura subjacente?

Se algum desses itens for atualmente desconhecido, eu também ficaria interessado em ouvir isso.

Obrigado!

Realmente não tenho referências para esses resultados - eles não são difíceis de provar depois que você entende o teorema de Ladner.

1. Não, para qualquer conjunto NP incompleto A, existe outro conjunto B estritamente entre A e SAT.

2. Essas classes de equivalência são conhecidas como graus polinomiais-muitos-um. Você pode incorporar qualquer poset finito nos graus abaixo de NP. Em particular, os graus não são totalmente ordenados ou com ramificações finitas.

3. Tudo isso depende do que você quer dizer com "interessante". Existe uma enorme teoria da estrutura de graus dos conjuntos computáveis ​​(veja o livro de Soare, por exemplo) e muitas dessas perguntas não foram atribuídas a conjuntos de tempos polinomiais. Por exemplo, você pode ter conjuntos NP A e B cuja junção é equivalente a SAT e cujo encontro é equivalente ao conjunto vazio?