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