تم النشر اليوم 2024/06/11 | كثير حدود غير قطعي

نظريات مهمة

P
⊆
R
P
⊆
N
P
{displaystyle Psubseteq RPsubseteq NP}
P
⊆
c
o
−
R
P
⊆
c
o
−
N
P
{displaystyle Psubseteq co-RPsubseteq co-NP}
N
P
⊆
E
P
{displaystyle NPsubseteq EXP}
إذا N
P
=
P
C
P
(
f
,
f
)
{displaystyle NP=PCP(f,f)} عندما: f
=
o
(
l
o
g
(
n
)
{displaystyle f=o(log(n)} حينها NP=P
إذا S
a
t
∈
P
{displaystyle Satin P} حينها NP=P أو بشكل عام إذا أي لغة في قسم NP كامل موجودة في P حينها NP=P

امثلة

مسألة الاكتفاء: {SAT={φ | φ satisfiable أي لغة كل الصيغ البوليانية التي يمكن اعطاء متغيراتها تعويض بحيث ان قيمتها تكون 1 (أو true)
مشكلة المخطط الكامل ضمن مخطط: {clique={(,k): G graph and k number , Is there clique of size k وهي لغة كل المخطوطات التي يمكن فيها مخطوط كامل بكبر k?
هاتان اللغتان هما NP كاملتين كذلك. {p:هل p عدد اولي ؟}=PRIME وهذه اللغة موجودة في P
مشكلة تلوين المخطط: باعطائنا مُخطط هل يمكن تلوينه بثلاثة الوان بحيث أن كل ضلع رأسيها ملونين بالوان مختلفة ؟
مشكلة التفكيك إلى جداء عوامل أولية: ايجاد العوامل الاولية لعدد ما .
باعطائنا دالتين متعددتي الحدود، فحص هل هما متطابقين .

تعريف

يوجد عدة تعريفات ل-NP ولعل اهمها هو التالي: لغة L
⊆
[ 0
,
1
] ∗
{displaystyle Lsubseteq [{0,1}]^{*}} متواجدة في NP إذا كان هناك متعدد حدود p
: N → N {displaystyle p:mathbb {N} to mathbb {N} } وآلة تيورنج متعددة الحدود M (أي ان عدد حسابات M هو دالة متعددة الحدود بطول المدخل أي انه يوجد متعدد حدود g
: N → N {displaystyle g:mathbb {N} to mathbb {N} } حيث ان كمية حسابات (M(x هو (|g(|x عندما x يعبر عن المدخل للالة M و-|x| هو طول المدخل) حيث انه لكل x
∈
0
,
1
∗
{displaystyle xin {0,1}^{*}} : x
∈
L ⟺ ∃
u
∈
[
0
,
1 ] p
( | x | )
:
M
(
x
,
u
)
=
1
{displaystyle xin Liff exists uin [0,1]^{p(|x|)}:M(x,u)=1}
إذا كان x
∈
L
{displaystyle xin L} و u
∈
[
0
,
1 ] p
( | x | )
{displaystyle uin [0,1]^{p(|x|)}} بحيث ان 1=(M(x,u حينها نسمي u اثبات أو برهان(certificate) ل-x ونسمي M آلة فاحصة(verifier)(لانها تفحص إذا كان x في L بواسطة برهان u). نعرف اولا زمن حساب لالة غير حتمية ثم نعرف NP ليكون كل لغة يمكن تقريرها بآلة تيورنج غير حتمية بحيث ان زمن حسابها متعدد الحدود،
تعريف NTIME: لكل دالة T
: N → N {displaystyle T:mathbb {N} to mathbb {N} } و- L
⊆
[
0
,
1 ] ∗
{displaystyle Lsubseteq [0,1]^{*}} بحيث ان L
∈
N
T
I
M
E
(
T
(
n
)
{displaystyle Lin NTIME(T(n)} إذا يوجد ثابت c>0 وأيضا يوجد NDTM cT(n)-time (آلة تيورنج غير حتمية) M بحيث: ∀
x
∈
[
0
,
1 ] ∗
:
x
∈
L ⟺ M
(
x
)
=
1
{displaystyle forall xin [0,1]^{*}:xin Liff M(x)=1} . حينها نعرف NP بالشكل التالي: N
P
= ⋃ c
∈ N N
T
I
M
E
( n c
)
{displaystyle NP=bigcup _{cin mathbb {N} }NTIME(n^{c})}
وهذا التعريف هو أول تعريف ل-NP. N
P
=
P
C
P
(
l
o
g
(
n
)
,
1
)
{displaystyle NP=PCP(log(n),1)}
في بداية التسعينات برهنت هذه النظرية لتفتح افق جديدة في علوم الحاسوب ونظرية PCP هي نظرية اساسية في علم التعقيد إذ انه بواسطة هذا التعريف باتت صورة المسائل التي هي NP كاملة التي يمكن اعطائها حل مقرب اوضح حيث نتج عن هذه النظرية الكثير من النتائج عن صعوبة تقريب حل مسائل NP كاملة.

تاريخ

في بداية الستينات من القرن العشرين، حاول العالم Karp حل مسألة التقرير لمسألة البائع المتجول وهذا كان بادئ الامر وبعد وقت قصير Rabin اسس نظرية التعقيد ووضع حجارة الاساس لها وكلمة التعقيد(complexity) ظهرت فقط في عام 1965 وبعدها تم تعريف متى تكون الخوارزمية «جيدة» وتم هذا بواسطة Edmonds، اما cook فقد عرف NP وP وكذلك عرف مسائل NP كاملة وبين ان SAT هي كذلك واظهر ان كل مسألة NP كاملة يمكن حلها بواسطة SAT وذلك يتم بواسطة دالة تحويل (reduction) وقد عرف Karp لاحقا مسائل NP كاملة منها TSP وعرفت هذه المسائل بقائمة karp ال-21 وفي عام 2000 تم رصد جائزة بمبلغ مليون دولار لمن يحل مسألة NP=P.

تصنيفات مهمة داخل NP

لعل أحد أهم التصنيفات في NP هو القسم P وهو قسم اللغات التي يمكن تقريرها بواسطة آلة تيورنج حتمية بوقت حدودي، وهذا القسم يعتبرا مهما لان كل هذه اللغات لها استخدام عملي في علم الحاسوب.
مسائل NP كاملة وهي قسم لغات يتوفر فيها شرطان:
اللغة في NP
يمكن اختصار أو تحويل (reduction) كل لغة في NP إلى هذه اللغة
تقريبا كل المسائل العملية موجودة في هذا القسم ولكن في حال ان N
P
≠
P
{displaystyle NPneq P} حينها لا يوجد لاي من هذه المسائل خوارزمية جيدة بمعنى انه لا توجد آلة تيورنج حتمية بوقت حدودي تقرر هذه اللغات. القسم RP
مسألة تقرير S في RP إذا يوجد خوارزمية احتمالية بوقت حدودي A بحيث ان ∀
x
∈
S
{displaystyle forall xin S} الاحتمال بأن الخوارزمية A تقرر x بشكل صحيح أكبر من 1
2
{displaystyle {frac {1}{2}}} أي: P
r
[
A
(
x
)
=
1
]
≥
1
2
{displaystyle Pr[A(x)=1]geq {frac {1}{2}}} ، ولكل x
∉
S
{displaystyle xnotin S} الخوارزمية لا تخطأ في تقرير x أي: P
r
[
A
(
x
)
=
0
]
=
1
{displaystyle Pr[A(x)=0]=1}
RP هو اختصار Randomized Polynomial time وهذا القسم يعتبر من الاقسام العملية وذلك بالرغم من عدم معرفة إذا ما RP=P حيث انه يمكن كتابة برامج احتمالية وهذا يمكننا من استخدام اللغات فيه، أحد أهم اللغات التي فيه والتي لا يعرف لها خوارزمية حتمية بوقت حدودي هي مسألة فحص إذا ما متعددا الحدود متساويين.

شرح مبسط

هي قسم(class) لغات، اللغة(language) في سياقنا هذا هي مجموعة سلاسل (strings) من رموز الابجدية (alphabet) ومسألة التقرير (Decision problem) هي باعطانا سلسلة(string) من الرموز هل هي موجودة باللغة ام لا أي:

L
⊆

Σ

∗

{displaystyle Lsubseteq Sigma ^{*}}

، ويوجد خوارزمية A بحيث ان A(s)=1 فقط إذا

s
∈
L

{displaystyle sin L}

. واللغات التي في NP هي التي يمكن حلها (أي حل مسألة التقرير) بواسطة آلة تيورنغ غير حتمية متعددة الحدود، ولعل هذا القسم من اللغات هو الأهم في نظرية التعقيد الحسابي إذ ان اللغات التي يحتويها تمتد إلى كل فروع علم الحاسوب والنتائج على هذا قسم NP يؤثر في كل علوم الحاسوب. الاسم NP هو اختصار ل- Non deterministic Polynomial time