11
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Let me make sure I have the quantifiers correct. Are you asking if "for all $M$, there exists an $M'$, such that $M'$ can efficiently solve the the output of $M$" is true? $\endgroup$ – Tyson Williams May 1 '13 at 13:46
  • $\begingroup$ @TysonWilliams: Yes, I've edited the wording slightly to try to make that clear. Your statement should be, I think, equivalent to mine! $\endgroup$ – usul May 1 '13 at 18:02
  • 1
    $\begingroup$ As Emanuele points out this is probably not what you are really looking for, you probably want to generate instance-solution pairs where solving the instance is "hard". Possibly related to what you are looking for: 1. David's answer here and 2. section 6 of Stephen A. Cook and David G. Mitchell, "Finding Hard Instances of the Satisfiability Problem: A Survey", 1997 $\endgroup$ – Kaveh May 1 '13 at 22:39
12
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Can you explain why it is equivalent? ... By "uniform", I mean "uniform model of computation" -- if we asked the question for circuits, the answer would be trivially yes: each $M'_n$ would hardcode either a one or a zero, depending on whether $M_n$ is satisfiable or not. $\endgroup$ – usul May 1 '13 at 17:41
  • 4
    $\begingroup$ Each $M$ gives a tally language in NP: $L_M =\{1^n: M(1^n) \text{ is satisfiable.}\}$. So if unary-NP is equal to unary-P, then $M'$ is the machine that decides $L_M$. In the other direction, take any tally language in NP and take $M$ to be the machine that reduces it to SAT. If $M'$ exists, then the tally language is also in P, so unary P = unary NP. For the second equivalence you can check Hartmanis et al. (but one direction is very easy) dl.acm.org/citation.cfm?id=808769 $\endgroup$ – Sasho Nikolov May 1 '13 at 23:07
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks very much for the answer, that's really cool! I was actually originally not thinking at all about hard instances, just about whether a deterministic $M'$ is guaranteed to exist. But I guess we get a potentially more interesting question by considering this average-case hardness and the construction with one-way functions is really cool. Thanks again. $\endgroup$ – usul May 2 '13 at 3:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.