שיחה:תורת החישוביות/כריעות שפות/רדוקציה חישובית

רדוקציות פוזיטיביות ונגטיביות

נראה לי שהדבר עלול לבלבל קצת את הרואים את החומר בפעם הראשונה. רדוקציה פוזיטיבית, לדוגמה זו שבדוגמה עם מציאת שני האיברים הזהים, מראה שאפשר למצוא פתרון לבעיה ע"י פתרון לבעיה אחרת. רדוקציה נגטיבית עושה ההיפך. אמנם קונספטואלית אין הבדל, אך עדיין נראה לי שמי שרואה את החומר בפעם הראשונה עלול להתבלבל קמעא. Atavory - שיחה 10:18, 23 בינואר 2012 (IST)

דוגמת הרדוקציה

החלפתי את דוגמת הרדוקציה, מהסיבה הבאה. פורמאלית, היה צריך להגדיר רדוקציה בעזרת שתי פונקציות, f וg. הראשונה ממירה את הבעיה לקלט אחר, השניה ממירה את התוצאה לתוצאת הבעיה ההמקורית. חלק מתנאי הרדוקציה הוא ששתי הפונקציות נתנות לחישוב. בדוגמה המקורית, הפונקציה g המובלעת איננה טריוויאלית לחלוטין, בעוד שבשאר הפרק כן. Atavory - שיחה 11:41, 23 בינואר 2012 (IST)