cc07a-a - question 7

[Tom]

can someone please explain the answer this question? With one
quantifier doesn't this question become parallel to SAT, which makes
it impossible to solve in P? does the n=log(m) play a significant role
in the answer?

Thanks!

[Ofir]

כן, זה בדיוק למה התשובה היא איך שהיא.

אם יש logm משתנים אז יש m השמות אפשריות, נכון? (שתיים ב<->לוג).
אז בעצם מה שצריך לעשות זה לעבור על m אפשרויות (שזה פולינומי (אפילו
לינארי?) באורך הקלט), ולזכור.