Question

k-clique
p
bipartite_graph

בהנחה ש-PNPP \neq NP הוכיחו/הפריכו:

השפה

}\}הגרף GG הוא גרף דו צדדי וקיים בו קליק בגודל kk L={G,k:L = \{G, k :

ב-PP.

1

Answers

נשים לב שקל להכריע אם גרף הוא דו צדדי. כמו כן, בגרף דו צדדי הקליק המקסימלי האפשרי הוא בגודל 2 וזה קיים אמ"מ קיימת קשת בגרף, ולכן ניתן להכריע את השפה בזמן פולינומי והיא שייכת ל-PP.

1
Feedback