| dbo:abstract
|
- In computational complexity theory, PPA is a complexity class, standing for "Polynomial Parity Argument" (on a graph). Introduced by Christos Papadimitriou in 1994 (page 528), PPA is a subclass of TFNP. It is a class of search problems that can be shown to be total by an application of the handshaking lemma: any undirected graph that has a vertex whose degree is an odd number must have some other vertex whose degree is an odd number. This observation means that if we are given a graph and an odd-degree vertex, and we are asked to find some other odd-degree vertex, then we are searching for something that is guaranteed to exist (so, we have a total search problem). (en)
- PPA é uma classe de complexidade, significando em inglês "Polynomial Parity Argument" (em português: Argumento de Paridade Polinomial). Introduzido por Christos Papadimitriou em 1994 (página 528), PPA é uma subclasse de TFNP. É uma classe de problemas de busca que podem ser demonstrados como totais através de uma aplicação do lema do aperto de mão: qualquer grafo não-direcionado que possui um vértice cujo grau é um número ímpar deve ter outro vértice cujo grau é um número ímpar. Essa observação implica que dado um grafo e um vértice de grau ímpar, e for pedido para encontrarmos outro vértice de grau ímpar, então estamos procurando por algo cuja existência é garantida (então, temos um problema de busca total). PPA é definida do seguinte modo. Suponha que temos um grafo cujos vértices são strings binárias de bits, e o grafo é representado por um circuito de tamanho polinomial que recebe um vértice como entrada e produz como saída os seus vizinhos. (Note que isso nos permite representar um grafo de tamanho exponencial sobre o qual podemos realizar exploração local com eficiência). Suponha também que um vértice específico (digamos o vetor composto apenas por zeros) possui um número ímpar de vizinhos. É necessário encontrar outro vértice de grau ímpar. Note que esse problema está em NP—dado uma solução, a sua corretude pode ser verificada através do circuito. Um problema de computação de funão pertence a PPA se ele admitir uma redução em tempo polinomial a esse problema de busca em grafo. Um problema é completo para a classe PPA se além disso, esse problema de busca em grafo for reduzível a esse problema. PPA contém PPAD como subclasse. Isso é porque o problema correspondente que define PPAD, conhecido como FIM DA LINHA, pode ser reduzido (de uma maneira simples) para o problema de busca acima para um vértice de grau ímpar adicionar (essencialmente, apenas ignorando as direções das arestas em FIM DA LINHA). Há uma versão não-orientada do lema de Sperner conhecidamente completo para PPA. O problema de busca para um segundo Ciclo Hamiltoniano em um grafo 3-regular é um membro de PPA, mas não se sabe se é completo para PPA. (pt)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 3978 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| rdf:type
| |
| rdfs:comment
|
- In computational complexity theory, PPA is a complexity class, standing for "Polynomial Parity Argument" (on a graph). Introduced by Christos Papadimitriou in 1994 (page 528), PPA is a subclass of TFNP. It is a class of search problems that can be shown to be total by an application of the handshaking lemma: any undirected graph that has a vertex whose degree is an odd number must have some other vertex whose degree is an odd number. This observation means that if we are given a graph and an odd-degree vertex, and we are asked to find some other odd-degree vertex, then we are searching for something that is guaranteed to exist (so, we have a total search problem). (en)
- PPA é uma classe de complexidade, significando em inglês "Polynomial Parity Argument" (em português: Argumento de Paridade Polinomial). Introduzido por Christos Papadimitriou em 1994 (página 528), PPA é uma subclasse de TFNP. É uma classe de problemas de busca que podem ser demonstrados como totais através de uma aplicação do lema do aperto de mão: qualquer grafo não-direcionado que possui um vértice cujo grau é um número ímpar deve ter outro vértice cujo grau é um número ímpar. Essa observação implica que dado um grafo e um vértice de grau ímpar, e for pedido para encontrarmos outro vértice de grau ímpar, então estamos procurando por algo cuja existência é garantida (então, temos um problema de busca total). (pt)
|
| rdfs:label
|
- PPA (complexity) (en)
- PPA (complexidade) (pt)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
