 |
צריך להיזהר כאן. משוואות דיופנטיות שייכות ל-RE; כלומר, אם יש למשוואה פתרון, אפשר יהיה למצא אותו, *תמיד*. הבעיה היא רק עם זיהוי משוואות ללא פתרון. לכן להגיד "אין נוסחה למציאת הפתרון" זה לא מדוייק.
אבל פרט לכך, אם אתה רוצה לנסות להוכיח פה משהו, תצטרך לתת הגדרות מדוייקות - מה הקלט, מה הרדוקציה, מה התחום וכו'. ייתכן שיתגלה פתאום שלא קל אפילו לבדוק את הפתרונות (כי הם גדולים מדי) או שההמרה למשוואות לוקחת זמן רב מדי, וכדומה. ואחרי זה, גם תצטרך להוכיח שלא קיים שום אלגוריתם שפותר את הבעיה ביעילות (זה שונה מאוד מ"מספר המספרים עליהם יש לעבור גדול" - אולי יש אלגוריתם שלא צריך לעבור על כל המספרים? צריך להוכיח שלא יכול להתקיים כזה).
|
 |
RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש