https://3rabica.org/index.php?action=history&feed=atom&title=%D9%83%D9%88-%D8%A5%D9%86_%D8%A8%D9%8Aكو-إن بي - تاريخ المراجعة2026-06-08T09:39:42Zتاريخ التعديل لهذه الصفحة في الويكيMediaWiki 1.43.7https://3rabica.org/index.php?title=%D9%83%D9%88-%D8%A5%D9%86_%D8%A8%D9%8A&diff=1645041&oldid=prevعبد العزيز: بوت: إصلاح التحويلات2022-12-14T03:53:11Z<p>بوت: إصلاح التحويلات</p>
<p><b>صفحة جديدة</b></p><div>{{لا مصدر|تاريخ=يناير 2022}}<br />
في علم التعقيد الحسابي '''co-NP''' هي المجموعة المُكملة ل-[[كثير حدود غير قطعي|NP]] أي: co-NP={0,1}<sup>*</sup> \ NP .<br />
==تعريف==<br />
نقول أنَّ اللغة L تابعة ل- co-NP إذا:<br />
<br />
يوجد آلة تيورنج M بحيث أنّ وقتها حدودي ويتحقق التالي: x ∈ L ⇔ ∀ q ∈ {0,1}<sup>poly(|x|)</sup> M(x,q)=1<br />
<br />
في حين أنَّ |x| هو طول المُدخل x .<br />
==علاقات مع اقسام أخرى==<br />
* معلوم انَّ P ⊆ co-NP<br />
* في حين انه غير معلوم العلاقة بين NP و- co-NP معظم علماء الحاسوب يؤمنون بشدة: co-NP ≠ NP<br />
* co-RP ⊆ co-NP<br />
==امثلة==<br />
* طوطولوجيا: باعطائنا صيغة بوليانية هل هي صحيحة لكل تعويض في المتغيرات؟<br />
* كما اوردنا سالفا كل مسألة في NP المُكمل لها في co-NP .<br />
* مسألة GNI , باعطائنا مخططان هل هما ليسا [[تساوي الشكل|متساويا الشكل]]؟<br />
<br />
== مراجع ==<br />
{{مراجع}}<br />
<br />
==انظر أيضا==<br />
* [[قسم تعقيد]]<br />
* [[نظرية التعقيد الحسابي]].<br />
* [[مسألة كثير حدود وكثير حدود غير قطعي|مسألة P=NP]]<br />
* [[خوارزمية]]<br />
{{أقسام تعقيد}}<br />
{{شريط بوابات|رياضيات|علم الحاسوب}}<br />
<br />
{{بذرة رياضيات}}<br />
<br />
[[تصنيف:أقسام التعقيد الحسابي]]<br />
[[تصنيف:معلوماتية نظرية]]</div>عبد العزيز