PPAD

PPAD is the class of total search problems reducible in polynomial time to End-of-Line, with a polynomial-time decoder converting a target solution into a solution of the original problem. Its name abbreviates polynomial parity argument, directed. The existence argument concerns endpoints of an implicitly described directed graph. It gives a search complexity class rather than a class of yes-or-no decision problems.

The PCP-for-PPAD conjecture asks for a quasilinear reduction from End-of-Line to generalized circuits that remains decodable when a positive constant fraction of gates are violated. A generalized circuit assigns values in to wires and imposes local approximate arithmetic, comparison, and Boolean constraints.