Class Description

FIXP: Fixed Point

The class of fixed point problems. In the framework of fixed point problems, an instance I is associated with a (continuous) function F_I, and a solution of I is a fixed point of F_I.

Properties of FIXP problems:

1. the function F_I is represented by an algebraic circuit over {+, -, *, /, max, min} with rational constants
2. there is a polynomial time algorithm that computes the circuit from I.

Every FIXP problem has Partial Computation, Decision, (Strong) Approximation, and Existence counterparts; these can all be solved in PSPACE.

The Nash equilibrium problem for 3 or more players is FIXP-complete.

Linear-FIXP = PPAD.

Defined in [EY07].

Linked From

No class.