# Questions tagged [fixed-points]

The tag has no usage guidance.

5 questions
Filter by
Sorted by
Tagged with
157 views

### Which version of KAKUTANI does lie in PPAD?

The seminal paper of Papadimitriou [1] claims that the computational search problem KAKUTANI is $\mathbf{PPAD}$-complete. Unfortunately, there are very few details. Many other papers and surveys cite ...
113 views

### The originator of the fixed point theorem for DCPOs

Pataraia proved in "A constructive proof of Tarski’s fixed-point theorem for dcpo's", presented in the 65th Peripatetic Seminar on Sheaves and Logic, in Aarhus, Denmark, November 1997 that in a ...
135 views

### Relationship between Pataraia's theorem and inductive-recursive definitions?

Pataraia's fixed point theorem gives a constructive proof of the fact that if you have a monotone function $f$ on a DCPO, then it has a least fixed point. I've frequently used this fixed point theorem ...
91 views

### Deciding reachability under iterated independent polynomial mapping

For any $1\leq i\leq m$, $f_i: \mathbb{Q}\rightarrow \mathbb{Q}$ is a polynomial mapping over $x_i$, where $\mathbb{Q}$ is the set of rationals. For $\vec{a}_0=(a_1, \cdots, a_m)\in \mathbb{Q}^m$, we ...
76 views

### Solving recurrence [closed]

Let $f(x) = 3/2 - \sqrt{2 - 8x^2}$. I am interested in the recurrence $Y_0 = 0$ and $Y_{i+1} = f(Y_i) = f(f(Y_{i-1})) = ... = f(f(f(f(... f(0) ...))))$. A quick plot shows that $Y_i$ converges to $1/6$...