The definition of a generator of hard instances + solutions

[עודד גולדרייך‎]

[This mal is written in response to several private queries.]

The said definition, which was sketched in our meeting,
can be found in Sec 7.1.1 of my "complexity book"
(available from http://www.wisdom.weizmann.ac.il/~oded/cc-book.html)

The said text also contain the proof to the bonus exercise, so if you
read
the proof there, do not bother to submit a copy of it...

Oded