निश्चित-बिंदु गणना

निश्चित-बिंदु गणना किसी दिए गए फ़ंक्शन के सटीक या अनुमानित निश्चित बिंदु (गणित) की गणना करने की प्रक्रिया को संदर्भित करती है। इसके सबसे सामान्य रूप में, हमें एक फ़ंक्शन f दिया गया है जो ब्रौवर निश्चित-बिंदु प्रमेय की स्थिति को संतुष्ट करता है, अर्थात: f निरंतर है और इकाई N-cube|d-cube को स्वयं मैप करता है। ब्रौवर निश्चित-बिंदु प्रमेय गारंटी देता है कि f का एक निश्चित बिंदु है, लेकिन प्रमाण रचनात्मक नहीं है। अनुमानित निश्चित बिंदु की गणना के लिए विभिन्न एल्गोरिदम तैयार किए गए हैं। ऐसे एल्गोरिदम का उपयोग अर्थशास्त्र में बाजार संतुलन की गणना के लिए, गेम थ्योरी में नैश संतुलन की गणना के लिए और गतिशील सिस्टम विश्लेषण में किया जाता है।

परिभाषाएँ

तीन निश्चित बिंदुओं वाले एक उदाहरण फ़ंक्शन का ग्राफ़

इकाई अंतराल को निरूपित किया जाता है $E:=[0,1]$, और इकाई N-घन|d-आयामी घन को E द्वारा निरूपित किया जाता है^घ. एक सतत फलन f को E पर परिभाषित किया गया है^घ (ई से^घस्वयं को)। अक्सर, यह माना जाता है कि f न केवल निरंतर है, बल्कि लिप्सचिट्ज़ निरंतर भी है, अर्थात, कुछ स्थिरांक L के लिए, $|f(x)-f(y)|\leq L\cdot |x-y|$ ई में सभी एक्स, वाई के लिए^घ.

F का एक 'निश्चित बिंदु' E में एक बिंदु x है^d ऐसा कि f(x) = x. ब्रौवर निश्चित-बिंदु प्रमेय द्वारा, ई से कोई भी निरंतर कार्य^d का अपने आप में एक निश्चित बिंदु होता है। लेकिन सामान्य कार्यों के लिए, एक निश्चित बिंदु की सटीक गणना करना असंभव है, क्योंकि यह एक मनमाना वास्तविक संख्या हो सकता है। निश्चित-बिंदु गणना एल्गोरिदम अनुमानित निश्चित बिंदुओं की तलाश करते हैं। अनुमानित निश्चित बिंदु के लिए कई मानदंड हैं। कई सामान्य मानदंड हैं:

• अवशिष्ट मानदंड: एक सन्निकटन पैरामीटर दिया गया है $\varepsilon >0$ , एकε-f का अवशिष्ट निश्चित-बिंदु E में एक बिंदु x है^घऐसे कि $|f(x)-x|\leq \varepsilon$, यहाँ कहाँ |.. अर्थात सभी d निर्देशांक में अंतर है $f(x)-x$ अधिक से अधिक होना चाहिए ε.
• पूर्ण मानदंड: एक सन्निकटन पैरामीटर दिया गया है $\delta >0$, f का एक δ-पूर्ण निश्चित-बिंदु E में एक बिंदु x है^घऐसे कि $|x-x_{0}|\leq \delta$, कहाँ $x_{0}$ f का कोई निश्चित बिंदु है।
• 'सापेक्ष मानदंड': एक सन्निकटन पैरामीटर दिया गया है $\delta >0$, f का एक δ-सापेक्ष निश्चित-बिंदु E में एक बिंदु x है^घऐसे कि $|x-x_{0}|/|x_{0}|\leq \delta$, कहाँ $x_{0}$ f का कोई निश्चित बिंदु है।

लिप्सचिट्ज़-निरंतर कार्यों के लिए, पूर्ण मानदंड अवशिष्ट मानदंड से अधिक मजबूत है: यदि एफ निरंतर एल के साथ लिप्सचिट्ज़-निरंतर है, तो $|x-x_{0}|\leq \delta$ तात्पर्य $|f(x)-f(x_{0})|\leq L\cdot \delta$. तब से $x_{0}$ f का एक निश्चित बिंदु है, इसका तात्पर्य है $|f(x)-x_{0}|\leq L\cdot \delta$, इसलिए $|f(x)-x|\leq (1+L)\cdot \delta$. इसलिए, एक δ-पूर्ण निश्चित-बिंदु भी एक है ε-अवशिष्ट निश्चित-बिंदु के साथ $\varepsilon =(1+L)\cdot \delta$.

निश्चित-बिंदु गणना एल्गोरिदम का सबसे बुनियादी चरण एक मान क्वेरी है: ई में कोई x दिया गया है^घ, द

फ़ंक्शन f 'मूल्यांकन' प्रश्नों के माध्यम से पहुंच योग्य है: किसी भी x के लिए, एल्गोरिदम f(x) का मूल्यांकन कर सकता है। किसी एल्गोरिदम की रन-टाइम जटिलता आमतौर पर आवश्यक मूल्यांकनों की संख्या द्वारा दी जाती है।

संविदात्मक कार्य

स्थिरांक L के साथ एक लिप्सचिट्ज़-निरंतर फ़ंक्शन को 'संकुचनात्मक' कहा जाता है यदि L < 1; इसे 'कमजोर-संकुचन' कहा जाता है यदि L ≤ 1. ब्रौवर की शर्तों को संतुष्ट करने वाले प्रत्येक संकुचनशील कार्य का एक अद्वितीय निश्चित बिंदु होता है। इसके अलावा, संविदात्मक कार्यों के लिए निश्चित-बिंदु गणना सामान्य कार्यों की तुलना में आसान है।

फ़ंक्शन पुनरावृत्ति का उपयोग करके एक निश्चित बिंदु की गणना करना

निश्चित-बिंदु गणना के लिए पहला एल्गोरिदम बानाच का निश्चित-बिंदु पुनरावृत्ति एल्गोरिदम था। बानाच निश्चित बिंदु प्रमेय|बानाच का निश्चित-बिंदु प्रमेय का तात्पर्य है कि, जब निश्चित-बिंदु पुनरावृत्ति को संकुचन मानचित्रण पर लागू किया जाता है, तो टी पुनरावृत्ति के बाद त्रुटि होती है $O(L^{t})$. इसलिए, δ-सापेक्ष निश्चित-बिंदु के लिए आवश्यक मूल्यांकनों की संख्या लगभग है $\log _{L}(\delta )=\log(\delta )/\log(L)=\log(1/\delta )/\log(1/L)$. सिकोरस्की और वोज्नियाकोव्स्की दिखाया गया कि जब आयाम बड़ा होता है तो बानाच का एल्गोरिदम इष्टतम होता है। विशेष रूप से, जब $d\geq \log(1/\delta )/\log(1/L)$, δ-सापेक्ष निश्चित-बिंदु के लिए किसी भी एल्गोरिदम के आवश्यक मूल्यांकन की संख्या पुनरावृत्ति एल्गोरिदम द्वारा आवश्यक मूल्यांकन की संख्या 50% से अधिक है। ध्यान दें कि जब एल 1 के करीब पहुंचता है, तो मूल्यांकन की संख्या अनंत तक पहुंच जाती है। वास्तव में, कोई भी परिमित एल्गोरिथ्म L=1 वाले सभी कार्यों के लिए δ-पूर्ण निश्चित बिंदु की गणना नहीं कर सकता है।

जब एल <1 और डी = 1, इष्टतम एल्गोरिदम सिकोरस्की और वोज्नियाकोव्स्की का 'फिक्स्ड प्वाइंट एनवेलप' (एफपीई) एल्गोरिदम है।इसका उपयोग करके δ-सापेक्ष निश्चित बिंदु पाया जाता है $O(\log(1/\delta )+\log \log(1/(1-L)))$ प्रश्न, और एक δ-पूर्ण निश्चित बिंदु का उपयोग करना $O(\log(1/\delta ))$ प्रश्न. यह निश्चित-बिंदु पुनरावृत्ति एल्गोरिथ्म से बहुत तेज़ है। जब d>1 लेकिन बहुत बड़ा नहीं है, और L ≤ 1, इष्टतम एल्गोरिथ्म आंतरिक-दीर्घवृत्ताभ एल्गोरिथ्म (दीर्घवृत्ताभ विधि पर आधारित) है। यह एक पाता है ε-अवशिष्ट निश्चित-बिंदु का उपयोग कर रहा है $O(d\cdot \log(1/\varepsilon ))$ मूल्यांकन. जब L<1, यह एक δ-निरपेक्ष निश्चित बिंदु का उपयोग करके पाता है $O(d\cdot [\log(1/\delta )+\log(1/(1-L))])$ मूल्यांकन.

शेलमैन और सिकोरस्की की गणना के लिए बीईफिक्स (बाइसेक्शन लिफाफा फिक्स्ड-पॉइंट) नामक एक एल्गोरिदम प्रस्तुत किया ε-केवल L ≤ 1 का उपयोग करते हुए, द्वि-आयामी फ़ंक्शन का अवशिष्ट निश्चित-बिंदु $2\lceil \log _{2}(1/\varepsilon )\rceil +1$ प्रश्न. वे बाद में समान सबसे खराब स्थिति की गारंटी लेकिन बेहतर अनुभवजन्य प्रदर्शन के साथ, BEDFix (बाइसेक्शन लिफाफा डीप-कट फिक्स्ड-पॉइंट) नामक एक सुधार प्रस्तुत किया। जब L<1, BEDFix का उपयोग करके δ-पूर्ण निश्चित-बिंदु की गणना भी की जा सकती है $O(\log(1/\varepsilon )+\log(1/(1-L)))$ प्रश्न.

शेलमैन और सिकोरस्कीकी गणना के लिए पीफिक्स नामक एक एल्गोरिदम प्रस्तुत किया ε-एल ≤ 1 के साथ एक डी-आयामी फ़ंक्शन का अवशिष्ट निश्चित-बिंदु, का उपयोग करते हुए $O(\log ^{d}(1/\varepsilon ))$ प्रश्न. जब एल <1, पीफिक्स को निष्पादित किया जा सकता है $\varepsilon =(1-L)\cdot \delta$, और उस स्थिति में, यह उपयोग करके δ-पूर्ण निश्चित-बिंदु की गणना करता है $O(\log ^{d}(1/[(1-L)\delta ]))$ प्रश्न. जब L 1 के करीब होता है तो यह पुनरावृत्ति एल्गोरिथ्म से अधिक कुशल होता है। एल्गोरिदम पुनरावर्ती है: यह (d-1)-आयामी कार्यों पर पुनरावर्ती कॉल द्वारा एक d-आयामी फ़ंक्शन को संभालता है।

विभिन्न कार्यों के लिए एल्गोरिदम

जब फ़ंक्शन f अवकलनीय होता है, और एल्गोरिदम इसके व्युत्पन्न (केवल f ही नहीं) का मूल्यांकन कर सकता है, तो अनुकूलन में न्यूटन की विधि का उपयोग किया जा सकता है और यह बहुत तेज़ है।

सामान्य कार्य

लिप्सचिट्ज़ स्थिरांक L > 1 वाले कार्यों के लिए, एक निश्चित-बिंदु की गणना करना बहुत कठिन है।

एक आयाम

1-आयामी फ़ंक्शन (डी = 1) के लिए, एक δ-पूर्ण निश्चित-बिंदु का उपयोग करके पाया जा सकता है $O(\log(1/\delta ))$ द्विभाजन विधि का उपयोग करते हुए प्रश्न: अंतराल से प्रारंभ करें $E:=[0,1]$; प्रत्येक पुनरावृत्ति पर, मान लीजिए कि x वर्तमान अंतराल का केंद्र है, और f(x) की गणना करता है; यदि f(x) > x तो x के दाईं ओर उप-अंतराल पर पुनरावृत्ति करें; अन्यथा, x के बाईं ओर के अंतराल पर पुनरावृत्ति करें। ध्यान दें कि वर्तमान अंतराल में हमेशा एक निश्चित बिंदु होता है, इसलिए बाद में $O(\log(1/\delta ))$ प्रश्न, शेष अंतराल में कोई भी बिंदु f का δ-पूर्ण निश्चित-बिंदु है। सेटिंग $\delta :=\varepsilon /(L+1)$, जहां L लिप्सचिट्ज़ स्थिरांक है, एक देता है ε-अवशिष्ट निश्चित-बिंदु, का उपयोग करना $O(\log(L/\varepsilon )=\log(L)+\log(1/\varepsilon ))$ प्रश्न.

दो या दो से अधिक आयाम

दो या दो से अधिक आयामों वाले कार्यों के लिए, समस्या अधिक चुनौतीपूर्ण है। शेलमैन और सिकोरस्कीसाबित हुआ कि, किसी भी पूर्णांक d ≥ 2 और L > 1 के लिए, d-आयामी L-लिप्सचिट्ज़ फ़ंक्शंस का δ-पूर्ण निश्चित-बिंदु खोजने के लिए अनंत-कई मूल्यांकन की आवश्यकता हो सकती है। प्रमाण विचार इस प्रकार है. किसी भी पूर्णांक टी> 1 के लिए, और मूल्यांकन प्रश्नों (संभवतः अनुकूली) के टी के किसी भी अनुक्रम के लिए, कोई दो कार्यों का निर्माण कर सकता है जो निरंतर एल के साथ लिप्सचिट्ज़-निरंतर हैं, और इन सभी प्रश्नों का एक ही उत्तर दे सकते हैं, लेकिन उनमें से एक के पास है एक अद्वितीय निश्चित-बिंदु (x, 0) पर है और दूसरे का एक अद्वितीय निश्चित-बिंदु (x, 1) पर है। टी मूल्यांकन का उपयोग करने वाला कोई भी एल्गोरिदम इन कार्यों के बीच अंतर नहीं कर सकता है, इसलिए δ-पूर्ण निश्चित-बिंदु नहीं ढूंढ सकता है। यह किसी भी परिमित पूर्णांक T के लिए सत्य है।

इसे खोजने के लिए फ़ंक्शन मूल्यांकन पर आधारित कई एल्गोरिदम विकसित किए गए हैं ε-अवशिष्ट निश्चित-बिंदु

• किसी सामान्य फ़ंक्शन के एक निश्चित बिंदु का अनुमान लगाने वाला पहला एल्गोरिदम 1967 में हर्बर्ट स्कार्फ द्वारा विकसित किया गया था। स्कार्फ का एल्गोरिदम एक ढूंढता है ε-स्पर्नर के लेम्मा के समान एक निर्माण में, एक पूर्ण-लेबल वाले आदिम सेट को ढूंढकर अवशिष्ट निश्चित-बिंदु।
• हेरोल्ड डब्ल्यू. कुह्न द्वारा एक बाद का एल्गोरिदम आदिम सेटों के बजाय सरल और सरल विभाजन का उपयोग किया गया।
• सरल दृष्टिकोण को और विकसित करते हुए, ओरिन हैरिसन मेरिल पुनरारंभ एल्गोरिथ्म प्रस्तुत किया।
• बी कर्टिस ईव्स होमोटॉपी एल्गोरिदम प्रस्तुत किया। एल्गोरिथ्म एक एफ़िन फ़ंक्शन से शुरू करके काम करता है जो एफ का अनुमान लगाता है, और निश्चित बिंदु का पालन करते हुए इसे एफ की ओर विकृत करता है। माइकल टॉड की एक किताब1976 तक विकसित विभिन्न एल्गोरिदम का सर्वेक्षण।
• डेविड गेल दिखाया गया है कि एन-डायमेंशनल फ़ंक्शन (यूनिट डी-डायमेंशनल क्यूब पर) के एक निश्चित बिंदु की गणना करना यह तय करने के बराबर है कि हेक्स (बोर्ड गेम) के डी-डायमेंशनल गेम में विजेता कौन है (डी खिलाड़ियों वाला एक गेम, प्रत्येक) जिसे d-घन के दो विपरीत फलकों को जोड़ने की आवश्यकता है)। वांछित सटीकता को देखते हुएε
  • केडी आकार का एक हेक्स बोर्ड बनाएं, जहां $k>1/\varepsilon$. प्रत्येक शीर्ष z इकाई n-घन में एक बिंदु z/k से मेल खाता है।
  • अंतर की गणना करें f(z/k) - z/k; ध्यान दें कि अंतर एक एन-वेक्टर है।
  • शीर्ष z को 1, ..., d में एक लेबल द्वारा लेबल करें, जो अंतर वेक्टर में सबसे बड़े समन्वय को दर्शाता है।
  • परिणामी लेबलिंग डी खिलाड़ियों के बीच डी-आयामी हेक्स गेम के संभावित खेल से मेल खाती है। इस गेम में एक विजेता होना चाहिए, और गेल जीत का रास्ता बनाने के लिए एक एल्गोरिदम प्रस्तुत करता है।
  • जीत की राह में, एक बिंदु ऐसा होना चाहिए जिसमें एफ_i(z/k) - z/k सकारात्मक है, और एक आसन्न बिंदु जिसमें f_i(z/k) - z/k नकारात्मक है। इसका मतलब यह है कि इन दोनों बिंदुओं के बीच f का एक निश्चित बिंदु है।

सबसे खराब स्थिति में, इन सभी एल्गोरिदम द्वारा आवश्यक फ़ंक्शन मूल्यांकन की संख्या सटीकता के द्विआधारी प्रतिनिधित्व में घातीय है, अर्थात $\Omega (1/\varepsilon )$.

क्वेरी जटिलता

हिर्श, क्रिस्टोस पापादिमित्रियोउ और वावसिस ने यह साबित किया फ़ंक्शन मूल्यांकन के आधार पर कोई भी एल्गोरिदम, जो एक पाता है ε-f का अवशिष्ट निश्चित-बिंदु, आवश्यक है $\Omega (L'/\varepsilon )$ फ़ंक्शन मूल्यांकन, जहां $L'$ फ़ंक्शन का लिप्सचिट्ज़ स्थिरांक है $f(x)-x$ (ध्यान दें कि $L-1\leq L'\leq L+1$). ज्यादा ठीक:

• 2-आयामी फ़ंक्शन (d=2) के लिए, वे एक टाइट बाउंड साबित होते हैं $\Theta (L'/\varepsilon )$.
• किसी भी d ≥ 3 के लिए, an ज्ञात करना ε-डी-आयामी फ़ंक्शन के अवशिष्ट निश्चित-बिंदु की आवश्यकता होती है $\Omega ((L'/\varepsilon )^{d-2})$ प्रश्न और $O((L'/\varepsilon )^{d})$ प्रश्न.

बाद वाला परिणाम घातांक में एक अंतर छोड़ देता है। चेन और डेंगअंतर को बंद कर दिया. उन्होंने यह साबित कर दिया कि, किसी भी d ≥ 2 और के लिए $1/\varepsilon >4d$ और $L'/\varepsilon >192d^{3}$, कंप्यूटिंग के लिए आवश्यक प्रश्नों की संख्या ε-अवशिष्ट निश्चित-बिंदु में है $\Theta ((L'/\varepsilon )^{d-1})$.

असतत निश्चित-बिंदु गणना

असतत फ़ंक्शन के उपसमुच्चय पर परिभाषित एक फ़ंक्शन है$\mathbb {Z} ^{d}$(डी-आयामी पूर्णांक ग्रिड)। कई अलग-अलग निश्चित-बिंदु प्रमेय हैं, जो उन स्थितियों को बताते हैं जिनके तहत एक अलग फ़ंक्शन का एक निश्चित बिंदु होता है। उदाहरण के लिए, 'आईमुरा-मुरोता-तमुरा प्रमेय' बताता है कि (विशेष रूप से) यदि एफ एक आयत उपसमुच्चय से एक फ़ंक्शन है$\mathbb {Z} ^{d}$स्वयं के लिए, और f हाइपरक्यूबिक दिशा-संरक्षण फ़ंक्शन है|दिशा-संरक्षण, तो f का एक निश्चित बिंदु है।

मान लीजिए f पूर्णांक घन से एक दिशा-संरक्षण फ़ंक्शन है $\{1,\dots ,n\}^{d}$ खुद को। चेन और डेंगसाबित करें कि, किसी भी d ≥ 2 और n > 48d के लिए, ऐसे निश्चित बिंदु की गणना करना आवश्यक है $\Theta (n^{d-1})$ कार्य मूल्यांकन.

चेन और डेंग एक अलग असतत-निश्चित-बिंदु समस्या को परिभाषित करें, जिसे वे 2D-BROUWER कहते हैं। यह एक असतत फलन f पर विचार करता है $\{0,\dots ,n\}^{2}$ जैसे कि, ग्रिड पर प्रत्येक x के लिए, f(x) - x या तो (0, 1) या (1, 0) या (-1, -1) है। लक्ष्य ग्रिड में एक वर्ग ढूंढना है, जिसमें सभी तीन लेबल होते हैं। फ़ंक्शन f को वर्ग को मैप करना होगा $\{0,\dots ,n\}^{2}$स्वयं के लिए, इसलिए इसे रेखाओं x = 0 और y = 0 को या तो (0, 1) या (1, 0) पर मैप करना होगा; रेखा x = n से या तो (-1, -1) या (0, 1); और रेखा y = n से या तो (-1, -1) या (1,0)। समस्या को '2D-SPERNER' तक कम किया जा सकता है (स्पर्नर के लेम्मा की शर्तों को पूरा करने वाले त्रिभुज में एक पूर्ण-लेबल वाले त्रिकोण की गणना करना), और इसलिए यह PPAD-पूर्ण है। इसका तात्पर्य यह है कि अनुमानित निश्चित-बिंदु की गणना बहुत सरल कार्यों के लिए भी पीपीएडी-पूर्ण है।

निश्चित-बिंदु गणना और रूट-फाइंडिंग एल्गोरिदम के बीच संबंध

E से एक फ़ंक्शन g दिया गया है^d से R तक, g का 'मूल' E में एक बिंदु x है^d ऐसा कि g(x)=0. एक 'ε-g का मूल E में एक बिंदु x है^घऐसे कि $g(x)\leq \varepsilon$.

फिक्स्ड-पॉइंट गणना रूट-फाइंडिंग का एक विशेष मामला है: ई पर एक फ़ंक्शन एफ दिया गया है^घ, परिभाषित करें $g(x):=|f(x)-x|$. स्पष्ट रूप से, x, f का एक निश्चित-बिंदु है यदि और केवल यदि x, g का मूल है, और x एक है ε-f का अवशिष्ट निश्चित-बिंदु यदि और केवल यदि x एक है ε-जी की जड़. इसलिए, किसी भी जड़-खोज एल्गोरिदम (एक एल्गोरिदम जो किसी फ़ंक्शन के अनुमानित रूट की गणना करता है) का उपयोग अनुमानित निश्चित-बिंदु खोजने के लिए किया जा सकता है।

इसके विपरीत सत्य नहीं है: किसी सामान्य फ़ंक्शन का अनुमानित मूल ढूँढ़ना किसी अनुमानित निश्चित बिंदु को ढूँढ़ने से अधिक कठिन हो सकता है। विशेष रूप से, सिकोरस्की यह साबित कर दिया कि एक खोज ε-रूट की आवश्यकता है $\Omega (1/\varepsilon ^{d})$ कार्य मूल्यांकन. यह एक-आयामी फ़ंक्शन के लिए भी एक घातीय निचली सीमा देता है (इसके विपरीत, एक ε-एक-आयामी फ़ंक्शन का अवशिष्ट निश्चित-बिंदु का उपयोग करके पाया जा सकता है $O(\log(1/\varepsilon ))$ द्विभाजन विधि का उपयोग कर प्रश्न)। यहाँ एक प्रमाण रेखाचित्र है। एक फ़ंक्शन g बनाएं जो इससे थोड़ा बड़ा हो ε ई में हर जगह^dकुछ बिंदु x के आसपास कुछ छोटे घन को छोड़कर₀, कहां एक्स₀ जी की अद्वितीय जड़ है. यदि g स्थिरांक L के साथ निरंतर लिप्सचिट्ज़ है, तो x के चारों ओर घन₀ की एक साइड-लंबाई हो सकती है $\varepsilon /L$. कोई भी एल्गोरिदम जो एक पाता है ε-जी के मूल को घनों के एक सेट की जांच करनी चाहिए जो पूरे ई को कवर करता है^घ; ऐसे घनों की संख्या न्यूनतम है $(L/\varepsilon )^{d}$.

हालाँकि, फ़ंक्शंस के ऐसे वर्ग हैं जिनके लिए अनुमानित मूल ढूंढना अनुमानित निश्चित बिंदु खोजने के बराबर है। एक उदाहरण कार्यों का वर्ग g इस प्रकार है $g(x)+x$ मानचित्र ई^dस्वयं के लिए (अर्थात: $g(x)+x$ ई में है^{ई में सभी एक्स के लिए डीघ}). ऐसा इसलिए है, क्योंकि ऐसे प्रत्येक फ़ंक्शन के लिए, function $f(x):=g(x)+x$ ब्रौवर के निश्चित-बिंदु प्रमेय की शर्तों को संतुष्ट करता है। स्पष्ट रूप से, x, f का एक निश्चित-बिंदु है यदि और केवल यदि x, g का मूल है, और x एक है ε-f का अवशिष्ट निश्चित-बिंदु यदि और केवल यदि x एक है ε-जी की जड़. चेन और डेंगदिखाएँ कि इन समस्याओं के अलग-अलग रूप कम्प्यूटेशनल रूप से समतुल्य हैं: दोनों समस्याओं की आवश्यकता है $\Theta (n^{d-1})$ कार्य मूल्यांकन.

संचार जटिलता

रफ़गार्डन और वीनस्टीन अनुमानित निश्चित-बिंदु की गणना की संचार जटिलता का अध्ययन किया। उनके मॉडल में, दो एजेंट हैं: उनमें से एक फ़ंक्शन f जानता है और दूसरा फ़ंक्शन g जानता है। दोनों कार्य लिप्सचिट्ज़ निरंतर हैं और ब्रौवर की शर्तों को पूरा करते हैं। लक्ष्य समग्र फ़ंक्शन के अनुमानित निश्चित बिंदु की गणना करना है $g\circ f$. वे दिखाते हैं कि नियतिवादी संचार जटिलता मौजूद है $\Omega (2^{d})$.

अग्रिम पठन

• Yannakakis, Mihalis (May 2009). "Equilibria, fixed points, and complexity classes". Computer Science Review. 3 (2): 71–85. doi:10.1016/j.cosrev.2009.03.004.