הצגת המקור של הדף "מחרוזות עצה"

בתורת החישוביות ובתורת הסיבוכיות, '''מחרוזת עצה''' היא כלי חישוב [[לא יוניפורמי]], שמייצג מחרוזת קבועה לכל אורך קלט אפשרי. מחרוזת עצה יכולה להיות מכל אורך שהוא, אך מחרוזת עצה מאורך [[פונקציה מעריכית|אקספוננציאלי]] גוררת מידית הכרעה של שפה אפשרית.
[[בעיית הכרעה]] A תוגדר להיות במחלקה <math>P/f(n)</math> אם מתקיימים התנאים הבאים: עבור כל <math>n \ \in N </math> קיימת מחרוזת עצה מאורך <math>f(n)</math> כך שקיימת [[מכונת טיורינג]] פולינומית דטרמיניסטית שמכריעה אותה בעזרת מחרוזת העצה.

השימוש הנפוץ ביותר במחרוזות עצה, הוא במחלקה [[P/Poly]], כלומר במחלקה בעלת מחרוזות עצה פולינומיות באורך בקלט. מתקיים: אם <math>NP\ \subseteq P/Poly</math>      [[ההיררכיה הפולינומית]] קורסת בדרגה 2. 

בהינתן מחרוזת עצה, אפילו באורך 1, ניתן להכריע בעיות [[כריעות|לא כריעות]], מכיוון שמחרוזת עצה באורך 1 מספיקה כדי להכריע [[שפה אונארית]], ולכן הרבה פעמים <math>P/f(n)</math> נחשבת למחלקה לא מציאותית, אם כי אפשר למצוא לה קירובים מציאותיים טובים.

[[קטגוריה:סיבוכיות חישובית]]