Qual é a complexidade de contar nós ímpares no gráfico?

De acordo com o lema do handshaking: qualquer gráfico não direcionado que tenha um vértice cujo grau seja um número ímpar deve ter outro vértice cujo grau seja um número ímpar. Essa observação significa que, se recebermos um gráfico e um vértice de grau ímpar, e formos solicitados a encontrar outro vértice de grau ímpar, procuraremos algo que é garantido que existe (portanto, temos um problema total de pesquisa )

O PPA (Christos Papadimitriou em 1994 [1]) é definido da seguinte forma. Suponha que tenhamos um gráfico em cujos vértices são cadeias binárias de n bits, e o gráfico é representado por um circuito de tamanho polinomial que pega um vértice como entrada e gera seus vizinhos. (Observe que isso nos permite representar um gráfico exponencialmente grande no qual podemos executar a exploração local com eficiência.) Suponha, além disso, que um vértice específico (digamos o vetor todos os zeros) tenha um número ímpar de vizinhos. Somos obrigados a encontrar outro vértice de grau ímpar. A classe correspondente de argumentos de paridade para gráficos direcionados pertence ao PPAD.

Minha pergunta: Qual é a complexidade da contagem de nós ímpares no gráfico direcionado e não direcionado?

[1] Papadimitriou, Christos H. "Sobre a complexidade do argumento da paridade e outras provas ineficientes da existência". Journal of Computer and system Sciences 48.3 (1994): 498-532.

Bem, pelo menos -hard. Dada uma fórmula SAT, construa um gráfico com dois vértices, e , para todas as atribuições possíveis de variáveis . Se é uma atribuição satisfatória para a fórmula, desenhe uma aresta entre e ; essas são as únicas arestas. É fácil construir o circuito para este gráfico a partir da fórmula SAT, e o número de vértices ímpares é exatamente o dobro do número de atribuições satisfatórias.$\#\mathsf{P}$$v_x$$v_x'$$\vec{x}$$x$$v_x$$v_x'$