Editing Knaster–Tarski theorem (section)

== Computing a Tarski fixed-point ==
Chang, Lyuu and Ti<ref>{{Cite journal |last1=Chang |first1=Ching-Lueh |last2=Lyuu |first2=Yuh-Dauh |last3=Ti |first3=Yen-Wu |date=2008-07-23 |title=The complexity of Tarski's fixed point theorem |url=https://www.sciencedirect.com/science/article/pii/S0304397508003812 |journal=Theoretical Computer Science |volume=401 |issue=1 |pages=228–235 |doi=10.1016/j.tcs.2008.05.005 |issn=0304-3975}}</ref> present an algorithm for finding a Tarski fixed-point in a [[Total order|totally-ordered]] lattice, when the order-preserving function is given by a [[value oracle]]. Their algorithm requires <math>O(\log L)</math> queries, where ''L'' is the number of elements in the lattice. In contrast, for a general lattice (given as an oracle), they prove a lower bound of <math>\Omega(L)</math> queries.

Deng, Qi and Ye<ref name=":0" /> present several algorithms for finding a Tarski fixed-point. They consider two kinds of lattices: componentwise ordering and [[lexicographic ordering]]. They consider two kinds of input for the function ''f'': [[value oracle]], or a polynomial function. Their algorithms have the following runtime complexity (where ''d'' is the number of dimensions, and ''N<sub>i</sub>'' is the number of elements in dimension ''i''): 
{| class="wikitable"
!{{ diagonal split header|Lattice|Input }}
!Polynomial function
!Value oracle
|-
|Componentwise
|<math>O(\operatorname{poly}(\log L)\cdot \log N_1 \cdots \log N_d) </math>
|<math>O(\log N_1 \cdots \log N_d) \approx O(\log^d L)</math>
|-
|Lexicographic
|<math>O(\operatorname{poly}(\log L)\cdot \log L) </math>
|<math>O(\log L)</math>
|}
The algorithms are based on [[binary search]]. On the other hand, determining whether a given fixed point is ''unique'' is computationally hard:
{| class="wikitable"
!{{ diagonal split header|Lattice|Input }}
!Polynomial function
!Value oracle
|-
|Componentwise
|[[coNP-complete]]
|<math>\Theta(N_1+\cdots+N_d)</math>
|-
|Lexicographic
|[[coNP-complete]]
|<math>\Theta(L)</math>
|}
For ''d''=2, for componentwise lattice and a value-oracle, the complexity of <math>O(\log^2 L)</math> is optimal.<ref>{{Cite journal |last1=Etessami |first1=Kousha |last2=Papadimitriou |first2=Christos |last3=Rubinstein |first3=Aviad |last4=Yannakakis |first4=Mihalis |date=2020 |editor-last=Vidick |editor-first=Thomas |title=Tarski's Theorem, Supermodular Games, and the Complexity of Equilibria |url=https://drops.dagstuhl.de/opus/volltexte/2020/11703 |journal=11th Innovations in Theoretical Computer Science Conference (ITCS 2020) |series=Leibniz International Proceedings in Informatics (LIPIcs) |location=Dagstuhl, Germany |publisher=Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik |volume=151 |pages=18:1–18:19 |doi=10.4230/LIPIcs.ITCS.2020.18 |doi-access=free |isbn=978-3-95977-134-4|s2cid=202538977 }}</ref> But for ''d''>2, there are faster algorithms:

* Fearnley, Palvolgyi and Savani<ref>{{Cite journal |last1=Fearnley |first1=John |last2=Pálvölgyi |first2=Dömötör |last3=Savani |first3=Rahul |date=2022-10-11 |title=A Faster Algorithm for Finding Tarski Fixed Points |url=https://doi.org/10.1145/3524044 |journal=ACM Transactions on Algorithms |volume=18 |issue=3 |pages=23:1–23:23 |doi=10.1145/3524044 |arxiv=2010.02618 |s2cid=222141645 |issn=1549-6325}}</ref> presented an algorithm using only <math>O(\log^{2\lceil d/3 \rceil} L)</math> queries. In particular, for ''d''=3, only <math>O(\log^2 L)</math> queries are needed.
* Chen and Li<ref>{{Cite book |last1=Chen |first1=Xi |last2=Li |first2=Yuhao |title=Proceedings of the 23rd ACM Conference on Economics and Computation |chapter=Improved Upper Bounds for Finding Tarski Fixed Points |date=2022-07-13 |chapter-url=https://dl.acm.org/doi/10.1145/3490486.3538297 |series=EC '22 |location=New York, NY, USA |publisher=Association for Computing Machinery |pages=1108–1118 |doi=10.1145/3490486.3538297 |arxiv=2202.05913 |isbn=978-1-4503-9150-4|s2cid=246823965 }}</ref> presented an algorithm using only <math>O(\log^{\lceil (d+1)/2 \rceil} L)</math> queries.