<h3>Question: Let <span class="math-container">$M\in \mathsf{PF}$</span> generate formulas. Does <span class="math-container">$\{ M(1^n) \mid  n\in \mathbb{N} \land M(1^n)\in SAT\}$</span> belong to <span class="math-container">$\mathsf{P}$</span>?</h3>
<p><span class="math-container">$succinctSAT \in \mathsf{E} \implies$</span> Yes:</p>
<p>The assumption about the generation of the formulas in polynomial time from <span class="math-container">$1^n$</span> means that the formula can be <em>succinctly</em> given. You want to decide their satisfiability in time <span class="math-container">$n^{O(1)}$</span>.</p>
<p>Given <span class="math-container">$\varphi = M(1^n)$</span> we can find an <span class="math-container">$n$</span> in polynomial time in <span class="math-container">$|\varphi|$</span>. Then <span class="math-container">$\varphi$</span> can be stated succinctly in <span class="math-container">$\lg n+O(1)$</span> bits using <span class="math-container">$M$</span> and <span class="math-container">$n$</span>. We can use our <span class="math-container">$succintSAT$</span> algorithm in <span class="math-container">$\mathsf{E}$</span> to decide this in time <span class="math-container">$2^{O(\lg n)} = n^{O(1)}$</span>.</p>
<p>Yes <span class="math-container">$\implies succinctSAT \in \mathsf{E}$</span>:</p>
<p>Let <span class="math-container">$M \in \mathsf{PF}$</span> s.t. given a circuit <span class="math-container">$C$</span> in <em>unary</em>, <span class="math-container">$M$</span> computes the string succinctly encoded by <span class="math-container">$C$</span>, and returns the result if it is a formula and <span class="math-container">$\bot$</span> otherwise.</p>
<p>Assume that <span class="math-container">$\{ M(1^n) \mid  n\in \mathbb{N} \land M(1^n)\in SAT\}$</span> belong to <span class="math-container">$\mathsf{P}$</span>. To solve <span class="math-container">$succinctSAT$</span> we write the given succinct formula in unary and then use our assumption to solve it.</p>
<h3>Question: Can we generate in polynomial-time instance-solution pairs for <span class="math-container">$SAT$</span> such that the instance is hard?</h3>
<p>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.</p>
<p>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 <span class="math-container">$n$</span> and finding <span class="math-container">$n$</span> 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).</p>
<blockquote>
<p>Is there an efficient (deterministic) algorithm <span class="math-container">$A$</span><br />
such that given a randomly chosen <span class="math-container">$k \in \{0,1\}^n$</span>,<br />
generates a pair of a SAT instances <span class="math-container">$\varphi_k$</span> and its answer <span class="math-container">$w_k$</span> such that<br />
no efficient (probabilistic/nonuniform) adversary algorithm <span class="math-container">$D$</span><br />
can correctly solve the SAT instances generated by <span class="math-container">$A$</span>  with non-negligible probability?</p>
</blockquote>
<p>Or more formally,</p>
<blockquote>
<p>Is there <span class="math-container">$A\in \mathsf{PF}$</span> such that for all <span class="math-container">$D \in \mathsf{P/poly}$</span>, such that
<span class="math-container">$SAT(A(k)_1) = A(k)_2$</span> for all <span class="math-container">$k$</span> and
<span class="math-container">$$\mathsf{Pr}_{k \in \{0,1\}^n} \{ D(A(k)_1) = SAT(A(K)_1) \} &lt; \frac{1}{poly(n)}$$</span></p>
</blockquote>
<p>It is easy to see that such a function can be turned into a one-way function as if it was easy to find <span class="math-container">$k$</span> from <span class="math-container">$\varphi_k$</span> then we can find the answer by computing <span class="math-container">$A(k)_2$</span>.</p>
<p>On the other hand, let <span class="math-container">$f$</span> be a one-way function. We can express <span class="math-container">$f(x)=y$</span> as a polynomial-size circuit since <span class="math-container">$f$</span> 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 <span class="math-container">$y$</span> as parameter and denote the resulting formula as <span class="math-container">$\varphi_{f,y}(x)$</span>. We can ask if there is any <span class="math-container">$x$</span> which satisfies <span class="math-container">$\varphi_{f,y}(x)$</span>. Any polynomial-time algorithm solving these <span class="math-container">$SAT$</span> instances with non-negligible probability will break the one-way function <span class="math-container">$f$</span>. 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 <span class="math-container">$f$</span>).</p>
<p>See also chapters 29 and 30 of Jan Krajicek's book &quot;Forcing with Random Variables&quot;, 2011 on <em>proof complexity generators</em>.</p>

CC BY-SA 3.0
2013-05-02T03:09:19.287Z
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.
usul
CC BY-SA 3.0
2013-05-02T00:35:43.847Z
2013-05-02T00:47:49.033Z
2020-06-17T09:38:08.363Z
Kaveh
<p>The question you are asking is equivalent to unary NP = unary P, which in turn is equivalent to NE = E, by padding.</p>

<p>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.</p>

<p>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 <a href="http://www.ccs.neu.edu/home/viola/papers/eh.pdf">The complexity of distributions</a>.</p>

CC BY-SA 3.0
2013-05-01T17:41:59.210Z
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.
usul
CC BY-SA 3.0
2013-05-01T23:07:40.147Z
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) http://dl.acm.org/citation.cfm?id=808769
Sasho Nikolov
CC BY-SA 3.0
2013-05-01T15:24:06.463Z
2013-05-01T15:24:06.463Z
Manu
<p>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 <em>Examiner's Problem</em> asks whether this is always possible; the <em>Examiner's Conjecture</em> states that, assuming, $\mathsf{P} \neq \mathsf{NP}$, it is <em>not</em>: coming up with problems is easier than coming up with their solutions.</p>

<p>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.</p>

<p>Assuming $\mathsf{P} \neq \mathsf{NP}$, has this question already been asked or answered? If not answered, what sorts of additional assumptions (<em>e.g.</em> 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?</p>

<p>Thanks!</p>

CC BY-SA 3.0
2013-05-01T13:46:24.040Z
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?
Tyson Williams
CC BY-SA 3.0
2013-05-01T18:02:53.190Z
@TysonWilliams: Yes, I've edited the wording slightly to try to make that clear. Your statement should be, I think, equivalent to mine!
usul
CC BY-SA 3.0
2013-05-01T22:39:24.537Z
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](http://cstheory.stackexchange.com/a/12352/186) and 2. section 6 of Stephen A. Cook and David G. Mitchell, "[Finding Hard Instances of the Satisfiability Problem: A Survey](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.9298)", 1997
Kaveh
<cc.complexity-theory><uniformity>
The Examiner's Problem (uniform generation of SAT decision instances/answers)
usul
# The Examiner's Problem (uniform generation of SAT decision instances/answers)

(Asked by: username_0 on 2013-05-01)

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!

**Tags:** cc.complexity-theory, uniformity
> **Comments:**
> **username_1**: 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?  
> **username_0**: @TysonWilliams: Yes, I've edited the wording slightly to try to make that clear. Your statement should be, I think, equivalent to mine!  
> **username_2**: 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](http://cstheory.stackexchange.com/a/12352/186) and 2. section 6 of Stephen A. Cook and David G. Mitchell, "[Finding Hard Instances of the Satisfiability Problem: A Survey](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.9298)", 1997  

---

## 2 answers

### Answer by username_3 on 2013-05-01. Score: 12 | Accepted answer

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](http://www.ccs.neu.edu/home/viola/papers/eh.pdf).

> **Comments:**
> **username_0**: 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.  
> **username_4**: 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) http://dl.acm.org/citation.cfm?id=808769  

---

### Answer by username_2 on 2013-05-02. Score: 4

### 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*.

> **Comments:**
> **username_0**: 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.  

---

