A course's teaching assistant has managed to write a program that (deterministically) generates difficult exam questions. Now, she'd like to write a program that generates the corresponding answers. The Examiner's Problem asks whether this is always possible; the Examiner's Conjecture states that, assuming, $\mathsf{P} \neq \mathsf{NP}$, it is not: coming up with problems is easier than coming up with their solutions.More formally, let $M$ be a deterministic Turing Machine that, on input $1^n$, generates in polynomial time a Boolean formula of size $n$. I'd like to know if, for all such $M$, there exists a deterministic polynomial-time Turing Machine $M'$ that, on input $1^n$, outputs $1$ if $M(1^n)$ has a satisfying assignment and $0$ otherwise.Assuming $\mathsf{P} \neq \mathsf{NP}$, has this question already been asked or answered? If not answered, what sorts of additional assumptions (e.g. one-way functions?) might bear on the result? Barring any of the above, my conjecture is that the answering TM does not always exist, but what is your intuition?Thanks!
The Examiner's Problem (uniform generation of SAT decision instances/answers)
cc.complexity theory;uniformity
The question you are asking is equivalent to unary NP = unary P, which in turn is equivalent to NE = E, by padding.From the title, perhaps you meant to ask if it is possible to generate input/output pairs such that the distribution on the inputs is hard.  The possibility of doing this lies somewhere between P $\ne$ NP and one-way functions exist.In restricted computational models, it is known that this is possible.  E.g. one can generate input/output pairs for the parity or majority functions in AC$^0$ or below.  See The complexity of distributions.