Content deleted Content added
Erel Segal (talk | contribs) |
Erel Segal (talk | contribs) |
||
Line 67:
Let ''f'' be a direction-preserving function from the integer cube {1,...,''n''}<sup>''d''</sup> to itself. Chen and Deng<ref name=":2" /> prove that, for any ''d'' ≥ 2 and ''n'' > 48 ''d'', computing such a fixed point requires <math>\Theta(n^{d-1})</math> function evaluations.
Chen and Deng<ref>{{Cite journal |last=Chen |first=Xi |last2=Deng |first2=Xiaotie |date=2009-10-17 |title=On the complexity of 2D discrete fixed point problem |url=https://www.sciencedirect.com/science/article/pii/S030439750900499X |journal=Theoretical Computer Science |series=Automata, Languages and Programming (ICALP 2006) |language=en |volume=410 |issue=44 |pages=4448–4456 |doi=10.1016/j.tcs.2009.07.052 |issn=0304-3975}}</ref> define a different discrete-fixed-point problem, which they call 2D-BROUWER. It considers a discrete function ''f'' on {0,...,''n''}''<sup>2</sup>'' such that, for every ''x'' on the grid, ''f''(''x'')-''x'' is either (0,1) or (1,0) or (-1,-1). The goal is to find a square in the grid, in which all three labels occur. The function ''f'' must map the square {0,...,''n''}<sup>''2''</sup> to itself, so it must map the lines ''x''=0 and ''y''=0 to either (0,1) or (1,0); the line ''x''=''n'' to either (-1,-1) or (0,1); and the line ''y''=''n'' to either (-1,-1) or (1,0). The problem can be reduced to 2D-SPERNER (computing a fully-labeled triangle in a triangulation satisfying the conditions to [[Sperner's lemma]]), and therefore it is [[PPAD-complete]]. This implies that computing an approximate fixed-point is PPAD-complete even for very simple functions.
== Relation between fixed-point computation and root-finding algorithms ==
| |||