Estudando sobre complexidade, me deparei com o termo NPI. Ele significa NP-intermediário. Mas não entendi o que é esse "intermediário".
- O que caracteriza um problema NPI? Por que ela tem esse nome?
- Existe diferença entre NPI e NPC?
- Alguma coisa muda em relação à essa classe caso se descubra a resposta ao problema P vs NP?
- Mais sobre NPC e P vs NP: O que é um problema NP completo?
- Mini-glossário para ajudar na pesquisa (mais detalhes na já existente resposta do @VictorStafusa):
- NP: não-determinístico polinomial
- P: determinístico polinomial
- NPC: NP-completo
- NPI: NP-intermediário