Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [fixed-points]

The tag has no usage guidance.

8
votes
0answers
148 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 ...
7
votes
1answer
109 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 ...
0
votes
1answer
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$...
1
vote
0answers
90 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 ...
6
votes
0answers
130 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 ...