| dbo:abstract
|
- In computational complexity theory, the complexity class PPP (polynomial pigeonhole principle) is a subclass of TFNP. It is the class of search problems that can be shown to be total by an application of the pigeonhole principle. Christos Papadimitriou introduced it in the same paper that introduced PPAD and PPA. PPP contains both PPAD and PWPP (polynomial weak pigeonhole principle) as subclasses. These complexity classes are of particular interest in cryptography because they are strongly related to cryptographic primitives such as one-way permutations and collision-resistant hash functions. (en)
- 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úmeros inteiros positivos que somados são inferiores a . O problema é encontrar dois diferentes subconjuntos de números que têm o mesmo total. (pt)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 7100 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- In computational complexity theory, the complexity class PPP (polynomial pigeonhole principle) is a subclass of TFNP. It is the class of search problems that can be shown to be total by an application of the pigeonhole principle. Christos Papadimitriou introduced it in the same paper that introduced PPAD and PPA. PPP contains both PPAD and PWPP (polynomial weak pigeonhole principle) as subclasses. These complexity classes are of particular interest in cryptography because they are strongly related to cryptographic primitives such as one-way permutations and collision-resistant hash functions. (en)
- 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 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. (pt)
|
| rdfs:label
|
- PPP (complexity) (en)
- PPP (complexidade) (pt)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
