सूचना दूरी

सूचना दूरी दो परिमित वस्तुओं के बीच की दूरी है जो सबसे छोटे कार्यक्रम में बिट्स की संख्या के रूप में व्यक्त की जाती है तथा यह एक वस्तु को दूसरी वस्तु या इसके विपरीत सार्वभौमिक कार्य में बदल देती है यह जटिलता का विस्तार है इसमें एकल परिमित वस्तु की समीकरण जटिलता उस वस्तु की जानकारी है जो परिमित वस्तुओं की एक जोड़ी के बीच की सूचना दूरी एक वस्तु या इसके विपरीत जाने के लिए आवश्यक न्यूनतम जानकारी है सूचना दूरी को पहली बार में परिभाषित की गई थी ऊष्मागतिकीय सिद्धांतों पर आधारित यह सामान्यीकृत संपीड़न दूरी और सामान्यीकृत दूरी में लागू होती है।

गुण

औपचारिक रूप से सूचना दूरी के $ID(x,y)$ बीच में $x$ और $y$ द्वारा परिभाषित किया गया है

$ID(x,y)=\min\{|p|:p(x)=y\;\&\;p(y)=x\},$

साथ $p$ सार्वभौमिक कंप्यूटर के लिए एक परिमित बाइनरी कार्यक्रम इनपुट के रूप में बाइनरी को परिभाषित करें इससे यह सिद्ध है कि$ID(x,y)=E(x,y)+O(\log \cdot \max\{K(x\mid y),K(y\mid x)\})$ साथ

$E(x,y)=\max\{K(x\mid y),K(y\mid x)\},$ जहाँ $K(\cdot \mid \cdot )$ समीकरण जटिलता है जिसे उपसर्ग द्वारा परिभाषित किया गया है।

सार्वभौमिकता

सार्वभौमिकता ऊपरी अर्द्धगणना योग्य दूरियों का वर्ग हो जैसे $D(x,y)$ जो घनत्व की स्थिति को संतुष्ट करता है।

$\sum _{x:x\neq y}2^{-D(x,y)}\leq 1,\;\sum _{y:y\neq x}2^{-D(x,y)}\leq 1,$

यह अप्रासंगिक दूरियों को बाहर करता है जैसे $D(x,y)={\frac {1}{2}}$ के लिए $x\neq y$ यह इस बात का ध्यान रखता है कि यदि दूरी बढ़ती है तो दी गई वस्तु की उस दूरी के भीतर वस्तुओं की संख्या बढ़ती है तो $D\in \Delta$ तब $E(x,y)\leq D(x,y)$ यह एक निरंतर योगात्मक शब्द तक की दूरी संभाव्यता अभिव्यक्तियाँ सूचना सममित में पहला वर्ग है जिसे सार्वभौमिकता संपत्ति के रूप में जाना जा सकता है।

मीट्रिक

दूरी $E(x,y)$ योज्य तक एक प्रवेशिका स्थान है जो $O(\log .\max\{K(x\mid y),K(y\mid x)\})$ प्रवेशिका 1981 में हॉर्न द्वारा दिखाया गया कि प्रवेशिका संभाव्य संस्करण में अद्वितीय है।

अधिकतम अतिच्छादन

अगर $E(x,y)=K(x\mid y)$ एक कार्यक्रम होता है तो $p$ लंबाई