PPP (complexidade)

PPP é uma classe de complexidade, abreviação de "Princípio Polinomial da Casa de Pombos". Introduzida por Christos Papadimitriou em 1994 (página 528), PPP é uma subclasse de TFNP. É uma classe de problemas de busca que pode ser mostrado como sendo total por uma aplicação do princípio da casa de pombos.

PPP é definida como segue. Um problema de computação de função pertence a PPP se admite uma redução de tempo polinomial para o problema do Circuito de Casa de Pombos ("PIGEONHOLE CIRCUIT"), em que a entrada consiste de um circuito booleano tendo o mesmo número de bits de entrada que o número de bits de saída, e uma solução consiste de um vetor de entrada que é mapeado para a saída 0, ou, alternativamente, dois vetores distintos de entrada que são mapeados para a mesma saída. Note que é o princípio da casa de pombos que garante que uma solução deve existir. Um problema é completo para a classe PPP se, além disso, PIGEONHOLE CIRCUIT é redutível ao problema.

PPP contém PPAD como uma subclasse. Isto ocorre porque o problema correspondente que define PPAD, conhecido como o FIM DA LINHA, pode ser reduzido (de uma forma direta) para o Circuito de Casa de Pombos.

No momento, os únicos problemas conhecidos por serem completos para PPP são variantes do Circuito de Casa de Pombos; esta é uma deficiência de PPP, uma vez que isso significa que a definição dessa classe até o momento falhou em capturar a complexidade de problemas adicionais. No entanto, a definição da classe PPP destaca a forma que o princípio da casa de pombos é uma generalização do "argumento de paridade em um grafo direcionado" princípio que garante que os problemas de busca pertencentes a PPAD são de fato totais. É uma questão em aberto se SUBCONJUNTOS IGUAIS é completa para PPP, onde SUBCONJUNTOS IGUAIS é definida da seguinte forma: A entrada consiste de um conjunto de $n$ números inteiros positivos que somados são inferiores a $2^{n}$. O problema é encontrar dois diferentes subconjuntos de números que têm o mesmo total.