מחרוזות עצה

בתורת החישוביות ובתורת הסיבוכיות, מחרוזת עצה היא כלי חישוב לא יוניפורמי, שמייצג מחרוזת קבועה לכל אורך קלט אפשרי. מחרוזת עצה יכולה להיות מכל אורך שהוא, אך מחרוזת עצה מאורך אקספוננציאלי גוררת מידית הכרעה של שפה אפשרית. בעיית הכרעה A תוגדר להיות במחלקה $P/f(n)$ אם מתקיימים התנאים הבאים: עבור כל $$\begin{gathered} n \\ \in N \end{gathered}$$ קיימת מחרוזת עצה מאורך $f(n)$ כך שקיימת מכונת טיורינג פולינומית דטרמיניסטית שמכריעה אותה בעזרת מחרוזת העצה.

השימוש הנפוץ ביותר במחרוזות עצה, הוא במחלקה P/Poly, כלומר במחלקה בעלת מחרוזות עצה פולינומיות באורך בקלט. מתקיים: אם $$\begin{gathered} NP \\ \subseteq P/Poly \end{gathered}$$ ההיררכיה הפולינומית קורסת בדרגה 2.

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