7 relações: Christos Papadimitriou, Circuito booliano, Completo (complexidade), PPAD, Princípio da casa dos pombos, Redução em tempo polinomial, TFNP.
Christos Papadimitriou
Christos Harilaos Papadimitriou (em grego: Χρήστος ΧαριλάουΠαπαδημητρίου; Atenas) é um Cientista da Computação da divisão de Ciência da Computação da Universidade da Califórnia em Berkeley, Estados Unidos.
Novo!!: PPP (complexidade) e Christos Papadimitriou · Veja mais »
Circuito booliano
Na teoria da complexidade computacional e complexidade de circuito, um circuito booliano é um modelo matemático para circuitos lógicos digitais.
Novo!!: PPP (complexidade) e Circuito booliano · Veja mais »
Completo (complexidade)
Na teoria da complexidade computacional, um problema computacional é completo para a classe de complexidade se ele está, tecnicamente falando, entre os "mais difíceis" (e os "mais expressivos") problemas da classe de complexidade.
Novo!!: PPP (complexidade) e Completo (complexidade) · Veja mais »
PPAD
Em ciência da computação, PPAD ("Polinômio de Paridade de Argumentos em Grafos Direcionados") é uma classe de complexidade introduzida por Christos Papadimitriou, em 1994.
Novo!!: PPP (complexidade) e PPAD · Veja mais »
Princípio da casa dos pombos
O princípio do pombal ou princípio da casa dos pombos é a afirmação de que se n pombos devem ser postos em m casas, e se n > m, então pelo menos uma casa irá conter mais de um pombo.
Novo!!: PPP (complexidade) e Princípio da casa dos pombos · Veja mais »
Redução em tempo polinomial
Na teoria da complexidade computacional uma redução em tempo polinomial é uma redução que é computável por uma máquina de turing determinística em tempo polinomial.
Novo!!: PPP (complexidade) e Redução em tempo polinomial · Veja mais »
TFNP
Na teoria da complexidade computacional, a complexidade de classe TFNP é uma subclasse da classe FNP onde existência da solução é garantida.
Novo!!: PPP (complexidade) e TFNP · Veja mais »