PPA (complexidade)

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 $n$ 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.