Exam 2007Ba

Exam 2007Ba

Eitan (guest) 26 Jan 2015 11:28

a few questions regarding the sol of the above exam (part B: closed questions):
1. In Q8 (Q3 in the sol), why in each level we sould pass only |Q|^2 states? as I understand, we start with q0, and checks which states we can arive from q0 (at most |Q|). then in the next level (I think about it as a states tree), we sould check which states we can arive from qi (in WC, i = 0, …, |Q|), so in this level in WC, we should pass through |Q|*|Q| = |Q|^2 states. In the following level, in the same manner, we we should pass through (|Q|^2)*|Q| = |Q|^3 states. and go on..
2. In Q10 (Q5 in the sol), is MaxClique NP-hard but not in NP or is it NPC? I think that the first option is true, because assume the k-size clique will be the wittness, we still have to check that there is no cliques of size > k.

Re: Exam 2007Ba

gal_rotem 26 Jan 2015 11:48

1. in each "level" (each level corresponds to reading another symbol from the input) we could "be" at at most |Q| states, from each such state we could move to at most |Q| states, that's why |Q| squared, I hope it's clearer now.
2. You are right, MaxClique is also coNP-hard, so it is unlikely to be in NP.