הועלה לאתר:  
מספר עמודים: 32
הורדת המסמך בגרסה להדפסהלהורדת המסמך בשלמותו

תורת החישוביות - חלק ראשון

סיכום מאת: ניר אדר

5.3. תכונות של רדוקציות

  1. כל שפה היא רדוקציה לעצמה: לכל שפה L מתקיים plot:\[L \leqslant L\]. (פונקצית הזהות).
  2. בהינתן 2 שפות plot:\[{L_1},{L_2}\] כך שמתקיים plot:\[{L_1} \leqslant {L_2}\] אזי מתקיים plot:\[\overline {{L_1}}  \leqslant \overline {{L_2}} \] (אותה רדוקציה).
  3. טרנזיטיביות של רדוקציות: יהיו plot:\[{L_1},{L_2},{L_3}\] כך שמתקיים: plot:\[{L_1} \leqslant {L_2}\] (plot:\[f\] היא פונקצית הרדוקציה) וכן plot:\[{L_2} \leqslant {L_3}\] (plot:\[g\] היא פונקציה הרדוקציה), אזי מתקיים: plot:\[{L_1} \leqslant {L_3}\], כאשר מתקיים כי plot:\[h\left( x \right) \triangleq g\left( {f\left( x \right)} \right)\] היא פונקציה הרדוקציה.
  4. היחס אינו סימטרי – קיימות plot:\[{L_1},{L_2}\] כך שמתקיים plot:\[{L_1} \leqslant {L_2}\] וכן plot:\[{L_2}\not  \leqslant {L_1}\], לדוגמא: plot:\[{L_1} \in R\] וגם plot:\[{L_2} = HP\].
  5. לכל plot:\[L \ne \phi \] מתקיים plot:\[L\not  \leqslant \phi \].

תגיות המסמך:

לפרק הקודם5.2. משפט הרדוקציה
לפרק הבא5.4. שימוש ברדוקציה – הוכחה ששפה אינה ב-CO-RE / RE
מאת: דנה

החלק הראשון

בבקשה
מאת: אני

http://www.underwar.co.il/download.asp?ID=407
http://www.underwar.co.il/download.asp?ID=299
מאת: רועי

אני חייב את המסמך הזה...הצילו

מאת: חשוון

מתי המסמך יחזור?
שיתוף:
| עוד