PPA (complexity)
id:
ppa-complexity-255-9035587
title:
PPA (complexity)
text:
In computational complexity theory, PPA is a complexity class, standing for "Polynomial Parity Argument". Introduced by Christos Papadimitriou in 1994, 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 a
brand slug:
wiki
category slug:
encyclopedia
description:
Complexity class
original url:
https://en.wikipedia.org/wiki/PPA_(complexity)
date created:
date modified:
2024-03-29T11:26:41Z
main entity:
{"identifier":"Q7120092","url":"https://www.wikidata.org/entity/Q7120092"}
image:
fields total:
13
integrity:
14