» נושאי לימוד
» נושאי לימוד
יום שבת 4 באפריל 2020
הגדרה פורמלית
דף ראשי  רדוקציות  הגדרה פורמלית גרסה להדפסה

הגדרה פורמלית

 

הרעיון : דרך לתרגם בעיה אחת לבעיה אחרת. ההוכחות בבעיית האימות נעשו ברדוקציה.

 

הגדרה:  יהיו   1*A Í å ,   2*B Í å שפות

רדוקצית התאמה מ -A ל B- הינה הפונקציה: 2* å ® 1* å f:  כך שלכל,  1 *,  XÎå                   f(X) ÎB  Û    XÎ A.

מתקיים אם B כריעה וקיימת רדוקצית התאמה מ- A ל- B שניתנת לחישוב אז גם A כריעה.

אנחנו רצינו להראות שאם Hany כרעיה אז גם H כריעה. בצענו רדוקציה מ – H ל- Hany הרדוקציה הייתה הפונקציה COMBINE . COMBINE(P,W) =PW כך ש-  H Î(P,W) Û

PW Î Hany. בדרך כלל השימוש ברדוקציה הוא בדרך השלילה כלומר בהינתן שפה

 A לא כריעה ורדוקציה ניתנת לחישוב מ- A ל B אז גם B לא כריעה.

 

 27-01-04 / 10:41  עודכן ,  01-01-04 / 13:38  נוצר ע"י שמרית דויטש  בתאריך 
 בעיית העצירה-2 - הקודםהבא - מתכונים 
תגובות הקוראים    תגובות  -  0
דרכונט
מהי מערכת הדרכונט?
אינך מחובר, להתחברות:
דוא"ל
ססמא
נושאי לימוד
חיפוש  |  לא פועל
משלנו  |  לא פועל
גולשים מקוונים: 7