In computer science, FIXP is a complexity class introduced by Kousha Etessami and Mihalis Yannakakis at 2010. [1] It represents problems that can be solved by computing a fixed point of a function that satisfies the conditions of Brouwer's fixed point theorem. More formally, FIXP contains search problem s that can be cast as fixed point computation problems for functions represented by algebraic circuits over basis {+,*,-,/,max,min} with rational constants.
They prove that some fundamental problems in economics and game theory are complete for FIXP, in particular:
Filos-Ratsikas, Hansen, Høgh and Hollender [2] present a general method for proving membership in FIXP. Their method constructs a black-box that they call “OPT-gate”, which can solve most convex optimization problems. Using their technique, they prove FIXP membership of:
They also prove FIXP membership for Nash equilibrium computation and for the mechanism of Hylland and Zeckhauser [3] for fair random assignment.
Etessami and Yannakakis describe the relation succinctly by saying that "The piecewise-linear fragment of FIXP equals PPAD". In other words, [4] the problems in PPAD are the problems in FIXP in which the input function is piecewise-linear.
Solutions to problems in PPAD are rational numbers, whereas solutions to problems in FIXP are algebraic number s. [5]
PPAD is contained in function classes that are in the intersection of NP and co-NP, whereas FIXP is conjectured to be much harder, and lie in the "harder" end of PSPACE. [5]
Computing an approximate Nash equilibrium to any factor smaller than 1/2 is at least as hard as the square-root sum problem.