תורת החישוביות/כריעות שפות/רדוקציה חישובית: הבדלים בין גרסאות בדף

תוכן שנמחק תוכן שנוסף
Atavory (שיחה | תרומות)
Atavory (שיחה | תרומות)
שורה 67:
*משני אלו נובעת התקפות של הרדוקציה. קל לראות שזו פונקציה מלאה וניתנת לחישוב ע״י מ״ט (כל שהמכונה נדרשת לעשות הוא החלפת הקידוד של מעבר ל־<math>q_{rej}</math> במעבר אחר).
 
==תכונות הרדוקציהבסיסיות של רדוקציות==
# לכל שפה 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>. (זוהי תכונת '''טרנזיטיביות''')