ZPP (जटिलता) - Revision history

Manidh at 16:12, 11 July 2023

2023-07-11T16:12:12Z

← Older revision		Revision as of 21:42, 11 July 2023
Line 80:		Line 80:

	{{ComplexityClasses}}		{{ComplexityClasses}}
	~~[[Category: संभाव्य जटिलता वर्ग]]~~

			[[Category:Collapse templates]]

	[[Category: ~~Machine Translated Page~~]]
	[[Category:Created On 27/06/2023]]		[[Category:Created On 27/06/2023]]
	[[Category:~~Vigyan Ready~~]]		[[Category:Machine Translated Page]]
			[[Category:Navigational boxes\| ]]
			[[Category:Navigational boxes without horizontal lists]]
			[[Category:Pages with script errors]]
			[[Category:Sidebars with styles needing conversion]]
			[[Category:Template documentation pages\|Documentation/doc]]
			[[Category:Templates generating microformats]]
			[[Category:Templates that are not mobile friendly]]
			[[Category:Templates using TemplateData]]
			[[Category:Wikipedia metatemplates]]
			[[Category:संभाव्य जटिलता वर्ग]]

Indicwiki: 13 revisions imported from :alpha:ZPP_(जटिलता)

2023-07-10T12:51:06Z

13 revisions imported from alpha:ZPP_(जटिलता)

← Older revision	Revision as of 18:21, 10 July 2023
(No difference)

alpha>Neeraja: added Category:Vigyan Ready using HotCat

2023-07-10T05:25:50Z

added Category:Vigyan Ready using HotCat

← Older revision		Revision as of 10:55, 10 July 2023
Line 86:		Line 86:
	[[Category: Machine Translated Page]]		[[Category: Machine Translated Page]]
	[[Category:Created On 27/06/2023]]		[[Category:Created On 27/06/2023]]
			[[Category:Vigyan Ready]]

alpha>Akanksha at 10:33, 5 July 2023

2023-07-05T10:33:00Z

← Older revision		Revision as of 16:03, 5 July 2023
Line 3:		Line 3:
	इस प्रकार से [[कम्प्यूटेशनल जटिलता सिद्धांत]] में, ZPP (शून्य-त्रुटि संभाव्य बहुपद समय) समस्याओं का [[जटिलता वर्ग]] है जिसके लिए इन गुणों के साथ [[संभाव्य ट्यूरिंग मशीन]] उपस्तिथ होती है:		इस प्रकार से [[कम्प्यूटेशनल जटिलता सिद्धांत]] में, ZPP (शून्य-त्रुटि संभाव्य बहुपद समय) समस्याओं का [[जटिलता वर्ग]] है जिसके लिए इन गुणों के साथ [[संभाव्य ट्यूरिंग मशीन]] उपस्तिथ होती है:

	* और यह सदैव हां या ना में सही उत्तर देते है। ~~'''या ना में सही सही'''~~		* और यह सदैव हां या ना में सही उत्तर देते है।
	* प्रत्येक इनपुट के लिए रनिंग टाइम अपेक्षा में बहुपद होते है।		* प्रत्येक इनपुट के लिए रनिंग टाइम अपेक्षा में बहुपद होते है।

alpha>Akanksha at 10:32, 5 July 2023

2023-07-05T10:32:46Z

← Older revision		Revision as of 16:02, 5 July 2023
Line 3:		Line 3:
	इस प्रकार से [[कम्प्यूटेशनल जटिलता सिद्धांत]] में, ZPP (शून्य-त्रुटि संभाव्य बहुपद समय) समस्याओं का [[जटिलता वर्ग]] है जिसके लिए इन गुणों के साथ [[संभाव्य ट्यूरिंग मशीन]] उपस्तिथ होती है:		इस प्रकार से [[कम्प्यूटेशनल जटिलता सिद्धांत]] में, ZPP (शून्य-त्रुटि संभाव्य बहुपद समय) समस्याओं का [[जटिलता वर्ग]] है जिसके लिए इन गुणों के साथ [[संभाव्य ट्यूरिंग मशीन]] उपस्तिथ होती है:

	* और यह सदैव हां या ना में सही उत्तर देते है। '''या ना में सही'''		* और यह सदैव हां या ना में सही उत्तर देते है। '''या ना में सही सही'''
	* प्रत्येक इनपुट के लिए रनिंग टाइम अपेक्षा में बहुपद होते है।		* प्रत्येक इनपुट के लिए रनिंग टाइम अपेक्षा में बहुपद होते है।

alpha>Akanksha at 10:32, 5 July 2023

2023-07-05T10:32:32Z

← Older revision		Revision as of 16:02, 5 July 2023
Line 3:		Line 3:
	इस प्रकार से [[कम्प्यूटेशनल जटिलता सिद्धांत]] में, ZPP (शून्य-त्रुटि संभाव्य बहुपद समय) समस्याओं का [[जटिलता वर्ग]] है जिसके लिए इन गुणों के साथ [[संभाव्य ट्यूरिंग मशीन]] उपस्तिथ होती है:		इस प्रकार से [[कम्प्यूटेशनल जटिलता सिद्धांत]] में, ZPP (शून्य-त्रुटि संभाव्य बहुपद समय) समस्याओं का [[जटिलता वर्ग]] है जिसके लिए इन गुणों के साथ [[संभाव्य ट्यूरिंग मशीन]] उपस्तिथ होती है:

	* और यह सदैव हां या ना में सही उत्तर देते है। '''या ना में सही ~~उत्तर देते है।~~'''		* और यह सदैव हां या ना में सही उत्तर देते है। '''या ना में सही'''
	* प्रत्येक इनपुट के लिए रनिंग टाइम अपेक्षा में बहुपद होते है।		* प्रत्येक इनपुट के लिए रनिंग टाइम अपेक्षा में बहुपद होते है।

alpha>Akanksha at 10:32, 5 July 2023

2023-07-05T10:32:22Z

← Older revision		Revision as of 16:02, 5 July 2023
Line 3:		Line 3:
	इस प्रकार से [[कम्प्यूटेशनल जटिलता सिद्धांत]] में, ZPP (शून्य-त्रुटि संभाव्य बहुपद समय) समस्याओं का [[जटिलता वर्ग]] है जिसके लिए इन गुणों के साथ [[संभाव्य ट्यूरिंग मशीन]] उपस्तिथ होती है:		इस प्रकार से [[कम्प्यूटेशनल जटिलता सिद्धांत]] में, ZPP (शून्य-त्रुटि संभाव्य बहुपद समय) समस्याओं का [[जटिलता वर्ग]] है जिसके लिए इन गुणों के साथ [[संभाव्य ट्यूरिंग मशीन]] उपस्तिथ होती है:

	* और यह सदैव हां या ना में सही उत्तर देते है।		* और यह सदैव हां या ना में सही उत्तर देते है। '''या ना में सही उत्तर देते है।'''
	* प्रत्येक इनपुट के लिए रनिंग टाइम अपेक्षा में बहुपद होते है।		* प्रत्येक इनपुट के लिए रनिंग टाइम अपेक्षा में बहुपद होते है।

alpha>Akanksha at 07:20, 4 July 2023

2023-07-04T07:20:04Z

alpha>Akanksha at 07:19, 4 July 2023

2023-07-04T07:19:22Z

alpha>Akanksha at 07:06, 4 July 2023

2023-07-04T07:06:01Z

← Older revision		Revision as of 12:36, 4 July 2023
Line 1:		Line 1:
	अन्य संभाव्य जटिलता वर्गों RP, co-RP, BPP, [[बीक्यूपी\|BQP]], PP[[पी (जटिलता)\|)]], (जटिलता) के संबंध में ZPP , जो PSPACE के अंदर P (जटिलता) को सामान्यीकृत करता है। यह अज्ञात है कि इनमें से कोई भी प्रतिबंध कठोर है या नहीं।		अन्य '''संभाव्य जटिलता''' वर्गों '''RP''', '''co-RP''', '''BPP''', [[बीक्यूपी\|BQP]], '''PP'''[[पी (जटिलता)\|)]], (जटिलता) के संबंध में ZPP , जो PSPACE के अंदर P (जटिलता) को सामान्यीकृत करता है। यह अज्ञात है कि इनमें से कोई भी प्रतिबंध कठोर है या नहीं।

	इस प्रकार से [[कम्प्यूटेशनल जटिलता सिद्धांत]] में, ZPP (शून्य-त्रुटि संभाव्य बहुपद समय) समस्याओं का [[जटिलता वर्ग]] है जिसके लिए इन गुणों के साथ [[संभाव्य ट्यूरिंग मशीन]] उपस्तिथ होती है:		इस प्रकार से [[कम्प्यूटेशनल जटिलता सिद्धांत]] में, ZPP (शून्य-त्रुटि संभाव्य बहुपद समय) समस्याओं का [[जटिलता वर्ग]] है जिसके लिए इन गुणों के साथ [[संभाव्य ट्यूरिंग मशीन]] उपस्तिथ होती है:

← Older revision		Revision as of 12:50, 4 July 2023
Line 4:		Line 4:

	* और यह सदैव हां या ना में सही उत्तर देते है।		* और यह सदैव हां या ना में सही उत्तर देते है।
	* प्रत्येक इनपुट के लिए रनिंग टाइम अपेक्षा में बहुपद होते है।		* प्रत्येक इनपुट के लिए रनिंग टाइम अपेक्षा में बहुपद होते है।

	किन्तु और दूसरे शब्दों में, यदि एल्गोरिदम को चलने के समय वास्तव में यादृच्छिक सिक्का फ्लिप करने की अनुमति दी जाती है, तो यह सदैव सही उत्तर देता है और आकार ''n,'' की समस्या के लिए, कुछ बहुपद ''p''(''n'') है जैसे कि औसत चल रहा है समय ''p''(''n'') से कम होगा, भले ही यह कभी-कभी बहुत अधिक हो सकता है। ऐसे एल्गोरिथम को [[ लास वेगास एल्गोरिथ्म \|लास वेगास एल्गोरिथ्म]] कहा जाता है।		किन्तु और दूसरे शब्दों में, यदि एल्गोरिदम को चलने के समय वास्तव में यादृच्छिक सिक्का फ्लिप करने की अनुमति दी जाती है, तो यह सदैव सही उत्तर देता है और आकार ''n,'' की समस्या के लिए, कुछ बहुपद ''p''(''n'') है जैसे कि औसत चल रहा है समय ''p''(''n'') से कम होगा, भले ही यह कभी-कभी बहुत अधिक हो सकता है। ऐसे एल्गोरिथम को [[ लास वेगास एल्गोरिथ्म \|लास वेगास एल्गोरिथ्म]] कहा जाता है।

	इस प्रकार से वैकल्पिक रूप से, '''ZPP''' को उन समस्याओं के वर्ग के रूप में परिभाषित किया जा सकता है जिनके अतिरिक्त लिए इन गुणों के साथ एक संभाव्य ट्यूरिंग मशीन उपस्तिथ होते है:		इस प्रकार से वैकल्पिक रूप से, '''ZPP''' को उन समस्याओं के वर्ग के रूप में परिभाषित किया जा सकता है जिनके अतिरिक्त लिए इन गुणों के साथ एक संभाव्य ट्यूरिंग मशीन उपस्तिथ होते है:
	* यह सदैव बहुपद समय में चलता है।		* यह सदैव बहुपद समय में चलता है।
	* इसका उत्तर हां, नहीं या पता नहीं है।		* इसका उत्तर हां, नहीं या पता नहीं है।
Line 18:		Line 18:

	== प्रतिच्छेदन परिभाषा ==		== प्रतिच्छेदन परिभाषा ==
	इस प्रकार से वर्ग ZPP, वर्ग RP और '''co-RP''' के प्रतिच्छेदन के पूर्ण रूप से समान होते है। इसे सदैव ZPP की परिभाषा के रूप में लिया जाता है। इसे प्रस्तुत करने के लिए , पहले ध्यान दें कि प्रत्येक समस्या जो ''दोनों'' RP और '''co-RP''' में है, उसका लास वेगास एल्गोरिदम इस प्रकार सम्मिलित किये जाते है:		इस प्रकार से वर्ग ZPP, वर्ग RP और '''co-RP''' के प्रतिच्छेदन के पूर्ण रूप से समान होते है। इसे सदैव ZPP की परिभाषा के रूप में लिया जाता है। इसे प्रस्तुत करने के लिए , पहले ध्यान दें कि प्रत्येक समस्या जो ''दोनों'' RP और '''co-RP''' में है, उसका लास वेगास एल्गोरिदम इस प्रकार सम्मिलित किये जाते है:

	* मान लीजिए कि हमारे पास भाषा L है जिसे RP एल्गोरिदम A और (संभवतः पूर्ण रूप से अलग) '''co-RP''' एल्गोरिदम B दोनों द्वारा मान्यता प्राप्त होती है।		* मान लीजिए कि हमारे पास भाषा L है जिसे RP एल्गोरिदम A और (संभवतः पूर्ण रूप से अलग) '''co-RP''' एल्गोरिदम B दोनों द्वारा मान्यता प्राप्त होती है।
	* किसी इनपुट को देखते हुए, चरण के लिए इनपुट पर A चलाएँ। यदि यह हाँ लौटाता है, तो उत्तर हाँ होना चाहिए। अन्यथा, चरण के लिए इनपुट पर B चलाएँ। यदि यह 'नहीं' लौटाता है, तो उत्तर 'नहीं' होना चाहिए। यदि ऐसा कुछ नहीं होता है, तो इस चरण को दोहराएँ।		* किसी इनपुट को देखते हुए, चरण के लिए इनपुट पर A चलाएँ। यदि यह हाँ लौटाता है, तो उत्तर हाँ होना चाहिए। अन्यथा, चरण के लिए इनपुट पर B चलाएँ। यदि यह 'नहीं' लौटाता है, तो उत्तर 'नहीं' होना चाहिए। यदि ऐसा कुछ नहीं होता है, तो इस चरण को दोहराएँ।

	इस प्रकार से ध्यान दें कि केवल मशीन ही गलत उत्तर दे सकती है, और प्रत्येक पुनरावृत्ति के समय उस मशीन के गलत उत्तर देने की संभावना अधिकतम 50% है। इसका मतलब यह है कि ''k'' वें समय तक पहुंचने की संभावना ''k'' में तीव्र से घट जाती है, जिससे पता चलता है कि यह [[अपेक्षित मूल्य]] चलने का समय बहुपद होते है। इससे पता चलता है कि '''RP''' इंटरसेक्ट '''co-RP''' ZPP में समाहित होते है।		इस प्रकार से ध्यान दें कि केवल मशीन ही गलत उत्तर दे सकती है, और प्रत्येक पुनरावृत्ति के समय उस मशीन के गलत उत्तर देने की संभावना अधिकतम 50% है। इसका मतलब यह है कि ''k'' वें समय तक पहुंचने की संभावना ''k'' में तीव्र से घट जाती है, जिससे पता चलता है कि यह [[अपेक्षित मूल्य]] चलने का समय बहुपद होते है। इससे पता चलता है कि '''RP''' इंटरसेक्ट '''co-RP''' ZPP में समाहित होते है।

	यह दिखाने के लिए कि ZPP '''RP''' इंटरसेक्ट '''co-RP''' में समाहित होते है, मान लीजिए कि हमारे पास समस्या को हल करने के लिए लास वेगास एल्गोरिदम C है। फिर हम निम्नलिखित '''RP''' एल्गोरिदम का निर्माण कर सकते हैं:		यह दिखाने के लिए कि ZPP '''RP''' इंटरसेक्ट '''co-RP''' में समाहित होते है, मान लीजिए कि हमारे पास समस्या को हल करने के लिए लास वेगास एल्गोरिदम C है। फिर हम निम्नलिखित '''RP''' एल्गोरिदम का निर्माण कर सकते हैं:
	* C को उसके अपेक्षित रनिंग समय से कम से कम ''दोगुने'' तक चलाएँ। यदि यह कोई उत्तर देता है तो वह उत्तर दीजिए। यदि यह हमारे रोकने से पहले कोई उत्तर नहीं देता है, तो 'नहीं' दें।		* C को उसके अपेक्षित रनिंग समय से कम से कम ''दोगुने'' तक चलाएँ। यदि यह कोई उत्तर देता है तो वह उत्तर दीजिए। यदि यह हमारे रोकने से पहले कोई उत्तर नहीं देता है, तो 'नहीं' दें।
	इस प्रकार से मार्कोव की असमानता के अनुसार, हमारे रोकने से पहले इसका उत्तर मिलने की संभावना कम से कम 1/2 है। इसका मतलब यह है कि हाँ उदाहरण पर हम रुककर और 'नहीं' देकर गलत उत्तर देंगे, यह समय अधिकतम 1/2 है, जो '''RP''' एल्गोरिथ्म की परिभाषा के अनुरूप है। '''co-RP''' एल्गोरिथ्म समान है, अतिरिक्त इसके कि यदि C का समय समाप्त हो जाता है तो यह हाँ देता है।		इस प्रकार से मार्कोव की असमानता के अनुसार, हमारे रोकने से पहले इसका उत्तर मिलने की संभावना कम से कम 1/2 है। इसका मतलब यह है कि हाँ उदाहरण पर हम रुककर और 'नहीं' देकर गलत उत्तर देंगे, यह समय अधिकतम 1/2 है, जो '''RP''' एल्गोरिथ्म की परिभाषा के अनुरूप है। '''co-RP''' एल्गोरिथ्म समान है, अतिरिक्त इसके कि यदि C का समय समाप्त हो जाता है तो यह हाँ देता है।
Line 44:		Line 44:
	* सह-अवधारणा पूरक सेट में गैर-सदस्यता, या सदस्यता का प्रमाण है।		* सह-अवधारणा पूरक सेट में गैर-सदस्यता, या सदस्यता का प्रमाण है।

	'''NP''', '''RP''' और ZPP वर्ग ऐसे सेट हैं जिनकी सदस्यता के लिए प्रमाण हैं। किन्तु वर्ग '''NP''' के लिए केवल यह आवश्यक है कि प्रमाण उपस्तिथ होते है । वे बहुत दुर्लभ हो सकते हैं. 2<sup>''f''(\|''x''\|)</sup> संभावित स्ट्रिंग, बहुपद के साथ f , सत्यापनकर्ता को स्वीकार करने के लिए केवल स्ट्रिंग की आवश्यकता होती है (यदि x, X में है। यदि x, X में नहीं है, तो कोई भी स्ट्रिंग सत्यापनकर्ता को स्वीकार करने का कारण नहीं बनेगी)।		'''NP''', '''RP''' और ZPP वर्ग ऐसे सेट हैं जिनकी सदस्यता के लिए प्रमाण हैं। किन्तु वर्ग '''NP''' के लिए केवल यह आवश्यक है कि प्रमाण उपस्तिथ होते है । वे बहुत दुर्लभ हो सकते हैं. 2<sup>''f''(\|''x''\|)</sup> संभावित स्ट्रिंग, बहुपद के साथ f , सत्यापनकर्ता को स्वीकार करने के लिए केवल स्ट्रिंग की आवश्यकता होती है (यदि x, X में है। यदि x, X में नहीं है, तो कोई भी स्ट्रिंग सत्यापनकर्ता को स्वीकार करने का कारण नहीं बनेगी)।

	अतः ''''RP'''<nowiki/>' और ' ZPP ' वर्गों के लिए यादृच्छिक रूप से चुनी गई कोई भी स्ट्रिंग संभवतः प्रमाण होगा ।		अतः ''''RP'''<nowiki/>' और ' ZPP ' वर्गों के लिए यादृच्छिक रूप से चुनी गई कोई भी स्ट्रिंग संभवतः प्रमाण होगा ।