The Examiner's Problem (uniform generation of SAT decision instances/answers)

Question

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!

Answer 1

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.

Answer 2

Question: Let $M\in \mathsf{PF}$ generate formulas. Does $\{ M(1^n) \mid n\in \mathbb{N} \land M(1^n)\in SAT\}$ belong to $\mathsf{P}$?

$succinctSAT \in \mathsf{E} \implies$ Yes:

The assumption about the generation of the formulas in polynomial time from $1^n$ means that the formula can be succinctly given. You want to decide their satisfiability in time $n^{O(1)}$.

Given $\varphi = M(1^n)$ we can find an $n$ in polynomial time in $|\varphi|$. Then $\varphi$ can be stated succinctly in $\lg n+O(1)$ bits using $M$ and $n$. We can use our $succintSAT$ algorithm in $\mathsf{E}$ to decide this in time $2^{O(\lg n)} = n^{O(1)}$.

Yes $\implies succinctSAT \in \mathsf{E}$:

Let $M \in \mathsf{PF}$ s.t. given a circuit $C$ in unary, $M$ computes the string succinctly encoded by $C$, and returns the result if it is a formula and $\bot$ otherwise.

Assume that $\{ M(1^n) \mid n\in \mathbb{N} \land M(1^n)\in SAT\}$ belong to $\mathsf{P}$. To solve $succinctSAT$ we write the given succinct formula in unary and then use our assumption to solve it.

Question: Can we generate in polynomial-time instance-solution pairs for $SAT$ such that the instance is hard?

We have to clarify what we mean by the instance being hard as any instance by itself is (theoretically) easy as it can be solved by either the algorithm that always says yes or the algorithm that always says no. It seems to me that you tried to get around this issue by imposing uniformity. Thinking in cryptographic terms, without some information that is not revealed to adversary there is no point in hiding the rest of computation as the adversary can simulate the protocol.

Assume that we have a polynomial-time algorithm that generate instance-solution pairs. The adversary can use the same algorithm to find the answer if it knows $n$ and finding $n$ is not difficult from the formula. The more reasonable way is to use a randomly chosen secret key to get around this and relax the hardness condition to be probabilistic: no polynomial-time algorithm can find a solution with high probability (without knowing the secret key).

Is there an efficient (deterministic) algorithm $A$
such that given a randomly chosen $k \in \{0,1\}^n$,
generates a pair of a SAT instances $\varphi_k$ and its answer $w_k$ such that
no efficient (probabilistic/nonuniform) adversary algorithm $D$
can correctly solve the SAT instances generated by $A$ with non-negligible probability?

Or more formally,

Is there $A\in \mathsf{PF}$ such that for all $D \in \mathsf{P/poly}$, such that $SAT(A(k)_1) = A(k)_2$ for all $k$ and $$\mathsf{Pr}_{k \in \{0,1\}^n} \{ D(A(k)_1) = SAT(A(K)_1) \} < \frac{1}{poly(n)}$$

It is easy to see that such a function can be turned into a one-way function as if it was easy to find $k$ from $\varphi_k$ then we can find the answer by computing $A(k)_2$.

On the other hand, let $f$ be a one-way function. We can express $f(x)=y$ as a polynomial-size circuit since $f$ is computable in polynomial-time (and we can turn it into a formula by introducing new variables for all gates and locally enforcing the condition for the correctness of the computation as in Tsien's translation). Let's consider $y$ as parameter and denote the resulting formula as $\varphi_{f,y}(x)$. We can ask if there is any $x$ which satisfies $\varphi_{f,y}(x)$. Any polynomial-time algorithm solving these $SAT$ instances with non-negligible probability will break the one-way function $f$. However this uses the fact that the adversary needs to find a witness not just the fact that the formula is satisfiable or not (but I think we can get around this issue by using the hard-bit of $f$).

See also chapters 29 and 30 of Jan Krajicek's book "Forcing with Random Variables", 2011 on proof complexity generators.