שתי שאלות ממועד א' האחרון

[eviatark]

בחלק האמריקאי:
שאלה 1, בהינתן גרף, האם קיים מסלול פשוט באורך 1/4n וגם קליק בגודל 4?
בהינתן עד של המסלול והקליק, לא ברור לי מדוע צריך זמן פולינומיאלי כדי
לוודא אותו. מדוע לא מספיק לוגריתמי?

שאלה 5, בהינתן גרף, האם קיימים 12n משולשים בדיוק?
לגבי זה אין לי מושג...

תודה!

[Eugene]

1. הבעיה היא לוודא מסלול פשוט ולא קליק. מכוון שזהו מסלול פשוט, חייבים
לחזור כל פעם בעד ולוודא שלא עברנו על אותו צומת פעמיים. מכוון שבהגדרה
של NL אסור לחזור בעד אחורה, אז זה לא יכול להיות במחלקה זו ולכן זה ב-
NP.
2. אין לי מושג

[odedr]

Eugene is correct about 1. You need to verify that the path is simple,
and this is something that we don't believe is possible in NL (i.e.,
with a logarithmic space verifier). It seems you really need
polynomial time verifier. (In your question you said "logarithmic
time", but this doesn't make much sense because in logarithmic time
you can't even read the input)

About your second question, you simply run over all (n choose 3) = O
(n^3) triples of vertices and count how many of them form a triangle.
Can't be simpler than that!

-- Oded