לכל אחת מבעיות ההכרעה שלהלן קבעו מהי מחלקת הסיבוכיות הקטנה ביותר ביחס להכלה שאליה ידוע שהי…

שאלה פתוחהq-95d0cabf2ab1

נוסח השאלה

לכל אחת מבעיות ההכרעה שלהלן קבעו מהי מחלקת הסיבוכיות הקטנה ביותר ביחס להכלה שאליה ידוע שהיא שייכת מבין המחלקות $P,NP,coNP,EXP$ . הוכיחו את קביעותיכם.

קלט: נוסחה בוליאנית $\varphi$ מצורת $CNF$ .
שאלה: האם קיימת השמה שאינה מספקת את $\varphi$ ?
קלט: נוסחה בוליאנית $\varphi$ מצורת $CNF$ .
שאלה: האם קיימת השמה שמספקת את $\varphi$ ?
קלט: נוסחה בוליאנית $\varphi$ מצורת $CNF$ .
שאלה: האם לכל היותר השמה אחת מספקת את $\varphi$ ?
קלט: נוסחה בוליאנית $\varphi$ מצורת $CNF$ .
שאלה: האם לכל היותר השמה אחת אינה מספקת את $\varphi$ ?
קלט: זוג נוסחאות בוליאניות $\varphi_1,\varphi_2$ מצורת $CNF$ .
שאלה: האם $\varphi_1$ ספיקה וגם $\varphi_2$ אינה ספיקה?

נוסח מטלה שנבדק אנושית.

Exact provenance

Each card is a genuinely distinct file. Printed versions inside one PDF stay in that card and do not inflate the sitting count.

Assignment

2025_04_תרגיל_4.md

Question 3Page 1Human reviewed