תורת החישוביות/כריעות שפות/רדוקציה חישובית: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ ←רדוקציות בין שפות: עיצוב, עקביות שם HP |
מ ←תכונות בסיסיות של רדוקציות: עיצוב |
||
שורה 68:
==תכונות בסיסיות של רדוקציות==
# לכל שפה L, מתקיים <math>L \le L</math> ע״י פונקציית הזהות.
# אם f היא רדוקציה מ־<math>L_1</math> ל־<math>L_2</math>, ו־g היא רדוקציה מ־<math>L_2</math> ל־<math>L_3</math>, אזי ההרכבה <math>g\circ f</math> היא רדוקציה מ־<math>L_1</math> ל־<math>L_3</math>. (זוהי תכונת '''טרנזיטיביות''')<center><math>L_1 \le L_2, L_2 \le L_3 \; \Rightarrow \; L_1 \le L_3</math></center>
#אם f היא רדוקציה מ־<math>L_1</math> ל־<math>L_2</math> אז אותה הפונקציה f היא גם רדוקציה מ־<math>\overline{L_1}</math> ל־<math>\overline{L_2}</math>. (נובע מהגדרת הרדוקציה)
| |||