سلم P
Sign in to saveAlso known as number P, sharp P, hash P, #P
In computational complexity theory, the complexity class #P (pronounced "sharp P" or, sometimes "number P" or "hash P") is the set of the counting problems associated with the decision problems in the set NP. More formally, #P is the class of function problems of the form "compute f(x)", where f is the number of accepting paths of a nondeterministic Turing machine running in polynomial time. Unlike most well-known complexity classes, it is not a class of decision problems but a class of function problems. The most difficult, representative problems of this class are #P-complete.
Wikidata facts
- Instance of
- complexity class
- Has part
- ♯P-complete
- Named after
- P
Sources (1)
via Wikidata · CC0
Article · العربية
في نظرية التعقيد P# هو صنف عد عدد مسارات الحساب التي هي «موافقة» في آلة تيورنج غير حتمية، وهذا القسم أو الصنف بخلاف كثير من الاقسام هو قسم دوال وليس مسائل تقرير. هناك علاقة قوية بين هذا القسم وبين القسم NP , حيث أن NP صيغة المسألة فيه «هل يوجد حل الذي يحقق ظروف معينة؟» اما P# فالصيغة هي: «ما هو عدد الحلول التي تحقق الظروف؟» مثال: المسائل التالية تابعة ل- NP : * هل يوجد قيم للمتغيرات في صيغة على شكل CNF حيث أنَّ الصيغة المُعطاة مكتفية؟ * هل يوجد في المُخطط المعطى مسار هاميلتوني؟ * هل يوجد مجموعة جزئية لمجموعة اعداد حيث ان مجموع المجموعة الجزئية 0 ؟ اما مسائل P# فهي كالتالي: * ما هو عدد التعويضات في القيم لصيغة بشكل CNF التي هي تجعل الصيغة مكتفية؟ * ما هو عدد المسارات الهاملتونية في مخطط معطى؟ * ما هو عدد المجموعات الجزئية التي مجموعها 0 ؟ لذا فاننا نعلم ان P# هي على الاقل مثل NP .
Abstract from DBpedia / Wikipedia · CC BY-SA