Homework 3 correction -- Problem 4

Hi -- as many of you noticed, the last part of Problem 4 does not look so doable :)

The result is in fact true -- indeed, $\Omega \left(\log n\right)$ hardness for Set-Cover is known even subject to P $\ne$ NP. However the method illustrated probably won't cut it.

Please do one of the following instead:

1. Use this method to prove $f\left(n\right)$-hardness for Set-Cover, for as large a function $f\left(n\right)$ as you can -- subject to NP not in DTIME($2^{o\left(n\right)}$) or an even better DTIME assumption.

OR

2. Prove $\Omega \left(\log n\right)$-hardness for Set-Cover assuming NP not in BPTIME($n^{polylogn}$) -- using any method.