Os problemas P são os que admitem solução determinística em tempo polinomial.
Os problemas NP são os que admitem solução não-determinística em tempo polinomial (ou seja, se você ver uma possível resposta em uma bola de cristal, poderá verificar se está ou não correta em tempo polinomial).
Os problemas NP-completos (NPC) são os "mais difíceis de NP", reduzindo-se em tempo polinomial uns aos outros. Há diversos problemas sabidamente NP-completos conhecidos por aí, tal como satisfatibilidade, caixeiro viajante, caminho hamiltoniano, etc. Se um deles for demonstrado estar em P, então todos os problemas de NP estariam em P e com isso P = NP.
Entretanto, tomando-se a premissa de que P ≠ NP, vem a pergunta: Será que todos os problemas que estão em NP obrigatoriamente estão em P ou em NPC? Ou será que haveria problemas em NP que não estão em nenhuma dessas duas categorias? Aí é que entra o NPI.
A classe NPI corresponde ao conjunto de problemas que estão em NP, mas não estão nem em NPC e nem em P. São problemas para os quais não há solução determinística em tempo polinomial (não estão em P), mas ainda assim uma possível solução pode ser verificada em tempo polinomial (estão em NP) e não são NP-completos:
Richard Ladner demonstrou em 1975, que se P ≠ NP então existem problemas dentro de NP que não estão nem em P e nem em NPC, foi com ele que surgiu a classe NPI. Ela tem esse nome (NP intermediário) porque não são nem os mais difíceis de NP (NPC) e nem os mais fáceis (P). Logo, estão em uma categoria intermediária.
Não se conhecem problemas reais que definitivamente estão em NPI. Até porque se para provar que um problema é NPI, você teria que provar que ele está em NP, mas está fora de P, e com isso você teria que provar primeiro que P ≠ NP antes de provar que algum problema particular está em NPI. Apesar disso, há alguns problemas suspeitos de estarem nessa área, os mais célebres são:
- Fatoração de números
- Logaritmo discreto
- Isomorfismo de grafos
Peguemos o problema da fatoração:
Seja x o número que você quer fatorar. Se você ver numa bola de cristal uma sequência de números primos que supostamente multiplicados resultam em x, você pode facilmente fazer a multiplicação e conferir se de fato eles produzem ou não x, logo esse problema está em NP.
Não se conhece algoritmo eficiente para fatorar-se números grandes. Supondo que de fato nenhum exista, então esse problema não está em P.
Não se conhece forma de reduzir-se o problema da satisfatibilidade ao problema da fatoração em tempo polinomial, e supondo que tal redução de fato não exista, o problema da fatoração não é NPC. De fato, os problemas NPC parecem ser significativamente mais complexos que o da fatoração.
Logo, se essas suposições forem verdadeiras, o problema da fatoração é NPI.