1. נגדיר את בעיית ההכרעה A כלהלן: קלט: נוסחה בוליאנית מצורת CNF ומספר טבעי k. שאלה: האם המספר המרבי של הסגרים…

נגדיר את בעיית ההכרעה $A$ כלהלן:

קלט: נוסחה בוליאנית $\varphi$ מצורת $CNF$ ומספר טבעי $k$.
שאלה: האם המספר המרבי של הסגרים שהשמה יכולה לספק בנוסחה $\varphi$ הוא בדיוק $k$?

1. הוכיחו כי $A$ היא $NP$-קשה וגם $coNP$-קשה. הסיקו כי אם $A\in NP\cup coNP$, אז $NP=coNP$.
2. הוכיחו כי $A\in\Sigma_2$.

הוכיחו כי

1. תנו דוגמה לשפה $PSPACE$-שלמה, והוכיחו שהיא כזו.

   הדרכה: אפשר להיעזר בתרגיל 2, שאלה 2ג.

2. הוכיחו כי אם $PSPACE=PH$, אז ההיררכיה הפולינומיאלית קורסת.