(a) One of the sources of sub-optimality of QM is the use of heuristics to choose a PI to break a cyclic PIT or RPIT.

Please help me with this one I'm totally lost, it's due tonight:

(a) One of the sources of sub-optimality of QM is the use of heuristics to choose a PI to break a cyclic

PIT or RPIT. Devise a simple method that is optimal in the case of a cyclic PIT or RPIT (state the

method clearly in words; a pseudo-code of the type given for QM in the notes is not needed, though

you can give one if you think it will be more explanatory).

Hint: Determine a subset of PIs in a cyclic PIT/RPIT, at least one of which needs to be in the final

solution (note that this does not mean that the others will not be in the final solution)—this is similar

to the idea in Petrick's, though this is not about devising a Petrick's-like technique but about devising

a QM+-like technique using this Petrick's-type idea. Using such a subset of PIs, explore different

ways for breaking the cyclic PIT; by definition, at least one of these will give an optimal solution.

(b) In a 2-level logic minimization problem in which a cyclic PIT or RPIT is encountered only once,

what will be the time-complexity of your method in notation (discussed in the notes).