数理解析研究所講究録
第 833 巻 1993 年 1-10

1co-NP 集合の NP 集合による近似について
岩間

一雄 \dag er

九州大学工学部情報工学科

iwama@csce.kyushu-u.ac.jp

1.

Introduction

if
is a subset of
in a classin a class $C_{1}app$ roximates a set
Let us say that a set
is said to be better than $B$ if $A\supset B$ and $A-B$. When bothand $B$ approximate $L,$
contains infinitely many elements. is called optimal if no better approximation than exists.
be the set of all satisfiable CNF predicates, $L_{neg-af}$ be the set of CNF
For example, letpredicates in which every clause includes both negative and affirmative literals. It is well known. It
is NP-complete. One can see easily that $L_{neg-af}$ is in and it approximates
that, the set of CNF predicates in which every clause includes at least one
also turns out thatnegative literal, is a better approximation than $L_{neg-af}$ . (The approximation is an independent
notion from the so-called subproblem: The satisfiability problem for some restricted domain (say,for Horn predicates) is clearly easier than the same problem for general CNF predicates. In the, namely, fordoes not have to be an easier class thancase of the approximation, the class
is P.)
is the family of NP-complete sets andexample, it does not loose any sense if$A$$L_{2}$$C_{2}$$L_{2}$$L_{1}$$L_{1}$

$A$

$A$

$A$

$L_{sat}$$P$$L_{sat}$$L_{sat}$$L_{neg}$$C_{2}$$C_{1}$$C_{2}$$C_{1}$

An apparent research goal is to seek better approximations in a different class, and that is
in which approximates
not new: A set
not in has been called P-levelable if for any set
$A$

$B$

$P$

$P$

which also approximates and is better than . Most natural
sets that are NP-complete, PSPACE- complete and so on are known to be P-levelable (under
the assumption that those sets are not in P), i.e., they have no optimal approximation (see thesummary in [2]). In this paper, we discuss the case whenis the class of NP-complete sets
(NPC) andis that of coNP-complete sets (coNPC). Its motivation and significance are as
follows:$A$, there exists another $B’$ in

$B$

$A$

$P$

$C_{1}$$C_{2}$

In [6] the present author et al. introduced the test-case generation with known answers

for the CNF satisfiability problem. Namely, our generator consists of two generators, one for
yes-instances (satisfiable predicates) and the other for no-instances (unsatisfiable predicates).
This allows us (i) to prepare test problems with their answers and (ii) to mix yes- and noinstances as we wish; both are very important in testing algorithms empirically. It turns outthat polynomial-time generatable sets are in NP. The set of all yes-instances,, is in NP
and can be generated in polynomial time in a relatively easy fashion (if we do not count the
distribution). However, the set of no-instances,, is in coNPC and cannot be generated inpolynomial time unless NP
co-NP. Thus we probably should try to generate not the whole$L_{sat}$$L_{\overline{sat}}$$=$$\uparrow Supported$by Scientific Research Grant, Ministry of Education, Japan, No. 02302047 and No. 04650318.

2
but its subset . Clearly should be as large as possible and must not be an easy subset
like one in P. The latter could be met by selecting as an NPC set. Thus our primary goal is.
to seek a good NPC approximation of
$S$

$S$

$L_{\overline{sat}}$$S$$L_{\overline{sat}}$

The first result in this paper is that as with the P-levelability mentioned above, there is. This is a somewhat good news for our motivation sinceno optimal NPC approximation of
it appears that we can get a better and better approximation without limit. Unfortunately thatis not a direct consequence of the result since its proof is nonconstructive. That is the reason
why the following second result makes sense: It is shown that there are an infinite sequenceis in NPC, each ; approximatessuch that eachof (explicit) sets
andis better thanfor each . We will also conjecture that a slight modification ofthis construction results in a constructive version of the first result, namely, that for any NPC, we can construct effectively a better approximation.
approximation of$L_{\overline{sat}}$$L_{0},$$L_{1},$$L_{i+1}$$L_{\overline{sat}}$$\cdots,$$L_{i},$$L_{1+1},$$L$$L_{i}$$\cdots$$i$$L_{i}$$L_{\overline{sa\ell}}$

As mentioned previously, it is expected that the present results will contribute to more
appropriate generation of test-cases or languages in general. Related works are as follows:
Sanchis et al. [11] shows that although most and NP languages appear to have polynomialtime generators, the question of whether
NP languages have such generators cannot be
resolved without answering some major open questions in complexity theory. One interesting
point is that the difficulty for NP languages is the same as that for languages in the case ofgeneration. There are many other papers which mainly focuses on the distribution of generated
instances, see [5, 3, 1]. Note that any of those works seldom mentions the generation of co-NP
languages. As for optimization problems, see $[10, 8]$ . See [13] for generation of several kindof graphs. Also recent papers $[9][12]$ have investigated both experimentally and theoreticallythat what kind of SAT instances are really hard (every SAT algorithm takes exponential time
almost always). Their claim is, not surprisingly, that if the instances are generated syntacticallyat random then those hard ones exist around such parameter values that the probability ofsatisfiability is 50%.
$P$

au

$P$

2.

Limitlessness of Better Approximation

Although most description in this section will be made by means of SAT, the statements themselves are not solely restricted to that particular problem. A literal is a logic variable orits negation . A clause is a sum of literals. A $(CNF)$ predicate is a product of clauses. A
specific assignment of true and false to all variables is called a cell. A predicate is said tobe satisfiable (unsatisfiable) if there is a (no) cell that makes true. It is said that a clausecovers a cell if the assignment denoted by makes A false. A clause is said to cover aclause if all the cells covered byare covered by A. (Intuitively, is larger than $B.$ )$x$$\overline{x}$

$f$

$A$

$f$

$T$

$B$

$T$

$B$

$A$

$A$

In proving our main theorem, we need mappings like the padding function [2]. Consider,3that are defined for predicates offor example, the following and$(x_{n+1})$$(x_{n+2})$
Note thatand
below are clauses including a single literal.
$\delta$$f$$\psi$$(x:_{1}^{1}))_{(\overline{x_{n+2}})}f(x_{n}^{n}$$\delta(f)=\{f$$ifnisevenifnisodd$$\psi(f)=\{f\cdot(x^{n}f\cdot(x_{n}\ddagger_{1}^{1}))_{(\overline{x_{n+2}})}$$ifnisevenifnisodd$.

$n$variables$x_{1}$, –,$x_{n}$:

Remark. has the following properties: As will be seen, they are important in the sensethat our later theorems hold for any specific mapping with these properties. Similarly for .
(i) is one-to-one.
(ii) is computable in polynomial time.
(iii)
is computable in polynomial time including the case that there is no predicate$\delta$$\psi$$\delta$$\delta$$\delta^{-1}$$g$such that $g=\delta^{-1}(f)$ , which is denoted byis larger than .
are disjoint, i.e., for any sets(iv) The size of
(v)

and

$\delta$$\psi$$\delta^{-1}(f)=\Lambda$.

$f$$\delta(f)$$A$

and $B$ of predicates, $\delta(A)\cap\psi(B)=\emptyset$ .

Before presenting our main theorem (NPC approximation of $coNP$ sets), we shall firstreview the result on the P-levelability ( approximation of harder sets) and make a slight
extension of that.
$P$

Proposition 1. Let
be a set of predicates that is not in
and is closed under the
mapping . (The predicates may be simply strings and the mapping may be any one having
the properties (ii) and (iv).) Then any approximationof is not optimal.
$A$

$P$

$\psi$$B$$P$

Proof [2]. Suppose that$B$

is optimal. A set

$C=$

$C$

$A$

is defined as follows:{ $f|f\not\in B$ but $\psi(f)\in B$ }As $B$ is in , and is computable in polynomial time,is also in P. Now consider, for eachin , the following sequence: $f,$ $\psi(f),$ $\psi^{2}(f)=\psi(\psi(f)),$. Since is closed under , eachvalue is in . Now the set
$P$

$f$

$C$

$\psi$$A$$\cdots$$A$$\psi$$A$$D_{f}=\{f, \psi(f), \psi^{2}(f), \cdots, \psi^{n}(f), \cdots\}$

is infinite and is insince
makes the size strictly larger. Because
was assumed to be
optimal,must eventually be contained in ; it must “cross” the boundary denoted by theset C.
$P$$B$$\psi$$B$$D_{f}$As$A-B$ is infinite. For each in $A-B$ , the sequence
is not inreaches somemember of and the size of is larger than that of . Thus only finitely many may reachany fixed , and hence there must be infinitely many such . Thus is infinite. Since $C\cap B=\emptyset$
by the definition of $C,$ $C\cup B$ contains infinitely more elements than $B$ and is still in
since
$B$
both
are in , which contradicts the assumption that
andis optimal.
$A$

$g$

$P,$

$C$

$f$

$g$

$g$

$D_{f}$

$f$

$f$

$g$

$C$

$P$

$C$

$B$

$P$

$\square$4
Proposition 2. Let
be a set of predicates that is not in NP and is closed underof is not optimal.
Then any NP approximation
$A$

$B$

$\psi$.

$A$

Proof. Almost the same as above but we define

$C$

as

$C=\{f|\psi(f)\in B\}$then we could
is in NP and so is $C\cup B$ as well. (If we would add the condition
are no longer disjoint, we can show thatis in NP.) Althoughandno longer claim that$C\cup B$ is infinitely larger thanby the similar argument as above.

Then

$C$

$f\not\in B$

$C$

$B$

$C$

$B$

$\square$Thus it was an easy extension of of Proposition 1 to prove the limitlessness of the better
NP approximation. As one can see, the key point in both proofs is to find the way of still
expanding the optimal approximation $B$ . The only condition in doing so is that the extension
must be made within , which is guaranteed by the mapping since it is closed within .
$A$

$A$

$\psi$

Now what would happen if the NP approximation is replaced by the NPC approximation?
Since $B$ is NP-complete, there are another NP-conplete set $X$ and a polynomial-time reduction. Then if we would try to expand $B$ as above, we havesuch thatandto pay attention to this set
since if the expansion of $B$ would imply an overlap between$B$ and, then the NP-completeness of $B$ would no longer be claimed. It should be noted.
), we have no specific information about thisthat unlike ( $i.e.$ , particular set$B\supseteq\alpha(X)$$\alpha$$\overline{B}\supseteq\alpha(\overline{X})$$\alpha(\overline{X})$$\alpha(\overline{X})$$A$$\alpha(\overline{X})$$L_{\overline{sat}}$

Theorem 1. Suppose that is a $coNP$ set of predicates and $B$ is an NPC approximationof such that both and are closed under and is closed under . (Again can be any
such mapping satisfying (ii) and (iv) and similarly for if it satisfies (i) to $(v).)$ Then if NP$coNP$ then $B$ is not optimal.
$A$

$A$

$A$

$\overline{B}$$\overline{A}$$\psi$$\delta$$\psi$$\delta$$\neq$

Proof. Since $B$ is NP-complete, there is another NP-complete set $X$ and a polynomialtime reduction such thatand. the first case to be considered is that
there are such $X$ and thatis in A. (In this case, two sets $B$ and are P-inseparable [4].
Recall thatcan be perfectly generatable and $B$ is probably so too since $B$ is in NP.
Then, although details are omitted, we were able to construct the so-called one-way function,
which no one has ever succeeded in. Thus, this first case seems to be a little unrealistic.) Thiscase is easy to treat since we can apply the same expansion of $B$ as Proposition 2. Clearly we
do not have to care about an overlap of $B$ withbecause the latter is outside .
$B\supseteq\alpha(X)$$\alpha$$\alpha$$\overline{B}\supseteq\alpha(\overline{X})$$\overline{A}$$\alpha(\overline{X})$$\overline{A}(=L_{sat})$$A$$\alpha(\overline{X})$

Hence, from now on, we can assume that there are no suchthe set $X$ and the reduction satisfies that. Let$\alpha$$\alpha(\overline{X})\cap A\neq\emptyset$$\alpha$and $X$ or that any pair of$C=\alpha(\overline{X})\cap A$

Now we show the following important property about this set

$C$

.

: Let

$C_{0}=\{\delta^{-\infty}(f)|f\in C\}$

where $g=\delta^{-\infty}(f)$ iffand for some $i\geq 0,$ $\delta^{i}(g)=f$ . Thenfollowing reason: Suppose hypothetically thatis finite. Then given in$\delta^{-1}(g)=\Lambda$$C_{0}$$C_{0}$$f$is infinite by the, we can$\alpha(X\cup\overline{X})$5
to repeatedly, which
decide whether is in or not in polynomial time. (One can apply.
then the sequence must end up in
makes shorter. If is inmust end shortly since
because of the closure property of
but never if is in
It may do so as well if is inthen
is not in
Now we can modify the reduction into the following : If$\alpha’(x)=\alpha(x)$ . Otherwise
is also
is some trivial element in . One can easily see thatpolynomial-time computable and it can act as a reduction just like . But this time
, which contradicts our current assumption.
or$f$$\delta^{-1}$$C$$\delta^{-1}$$\overline{A}$

$f$

$C$

$f$

$f$

$C_{0}$$\alpha(X)$$f$$\alpha’$$\delta.)$$f$$C_{0}$$\delta^{-\infty}\cdot\alpha(x)$$\alpha$$\alpha’$$\overline{A}$$\alpha’(x)$$\alpha’(\overline{X})\subseteq\overline{A}$$\alpha$$\alpha’(\overline{X})\cap A=\emptyset$

Now let $D=\delta(C)$ and$E=${$f|\delta^{-1}(f)\in B$, ol

and $\psi(f)\in B$ }$\delta^{-1}(f)=\Lambda$

by the closure property of and .
$B$
and are polynomially computable functions, $E$ is also in(ii) Since
is in NP and(i)$E\subseteq A$$\delta$$\delta^{-1}$$\psi$$\psi$

NP.
must be in by the definition of $D$ . Either
is in $D,$$\delta^{-1}(f)\in B$ orcontradicts this fact because and are disjoint.)
must be finite.
(iv) The difference $C-D$ is infinite. Otherwise the above(v) The difference $E-B$ is infinite: Apply
to each in the infinite $C-D$ repeatedly.
.
is in for the first time andThen it eventually reach suchor thatandis also infinite. If the set
Since $C-D$ is infinite and is one-to-one, the set of thoseis infinite then so is $E-B$ since such
exists in $E-B$ . Hence suppose that the set ofof,is infinite. Then we can use the argument of Proposition 2 considering the sequence, to show that $E-B$ is infinite. It should be noted that this sequence never goes into
because of the property (v) of and .
(iii) $E\cap D=\emptyset$ . (Reason: If$C$$\delta^{-1}(f)$

$f$

$B$

$\delta^{-1}(f)=\Lambda$$C$$C_{0}$$\delta^{-1}$$g_{1}$$f$$B$$\delta^{-1}(g_{1})$$g_{2}$$\delta^{-1}(g_{2})=\Lambda$$\delta$$g_{1}$$g_{2}$$g_{1}$$g_{1}$$\psi(g_{2})$$g_{2}$$\psi^{2}(g_{2}),$$\cdots$$D$$\delta$$\psi$

Now we obtained E U which is a subset of ((i) above) and is infinitely larger thanthat is clearly((v) above). It remains to show that $E\cup B$ is NPC: We modify intopolynomial-time computable.
includes $D$ and maybe some members in , which does
must beby the closure property of . Also
not overlap with $E$ by (iii) or withcontained in $E\cup B$ since
is in and contains such that for some in $B,$ $\delta(g)=f$ .
$B$

$A$

$B$

$\alpha$$\delta\cdot\alpha$$\overline{A}$$\delta\cdot\alpha(\overline{X})$$B$$\alpha(X)$$B$$\delta\cdot\alpha(X)$$\delta$$E$$f$$\square$$g$

It should be noted again that the proof does not depend on any specific property of SAT,
or . For many other natural problems, it does not seem to be so hard to find and thatsatisfy the condition (i) to (v) and the closure property described in the theorem.
$\delta$3.

$\delta$$\psi$$\psi$

Sequence of Better Approximations.

Suppose that we have an NPC approximation of. Then Theorem 1 says that there does
exist another NPC approximation that is better than but says nothing about how to get. At present we cannot find such a method, but can show an infinite sequence of better andbetter approximations each of which is constructed effectively.
$A$

$B$

$B$

$L_{\overline{sat}}$$A$

6
A CNF predicate is said to be provable if for some variable , xhi is implied fromapplying the following three operations repeatedly:(i) An arbitrary literal is added to an arbitrary clause .
(ii) Two clauses $(A+x)(A+\overline{x})$ are merged into a single clause .
(iii) An arbitrary clause is duplicated to $AA$ .
$f$

$x$

$f$

by

$A$

$A$

$A$

. Then is
Example. Let
is added to this $(x_{2}+x_{3})$ andprovable as follows: By operation (iii), $(x_{2}+x_{3})$ is duplicated.
.
is added to the other $(x_{2}+x_{3})$ and then
then merged withto imply.
to get $(x_{1}+x_{3})$ . Now became
merged with.
By merging the 1st and 3rd and also the 2nd and 4th, we get$f$$f=(\overline{x_{1}}+\overline{x_{2}})(x_{1}+\overline{x_{3}})(x_{2}+x_{3})(\overline{x_{1}}+x_{2}+\overline{x_{3}})(x_{1}+\overline{x_{2}}+x_{3})$$\overline{x_{1}}$$(\overline{x_{1}}+x_{2})$$(\overline{x_{1}}+x_{2}+\overline{x_{3}})$$x_{1}$$f$$(x_{1}+\overline{x_{2}}+x_{3})$$(\overline{x_{1}}+\overline{x_{2}})(x_{1}+\overline{x_{3}})(\overline{x_{1}}+x_{2})(x_{1}+x_{3})$$\overline{x_{1}}x_{1}$Note that among the three operations, only the third one increases the number of clauses.
Let $d(n)$ be a function in an integer . Then $PRV(d(n))$ denotes the set of predicates suchthat is provable by using operation (iii) at most $d(n)$ times where is the number of clauses
in . Then it is not hard to see that:(a) $PRV(d(n))$ approximates
for any $d(n)$ .
(b) $PRV(0)$ is in NP.
(c) $PRV(d(n))$ is still in NP if $d(n)$ is a polynomial.
Further results are shown in $[6, 7]$ :(d) $PRV(d(n))$ can be generated in polynomial time if $d(n)$ is a polynomial. (The generation is simply a reverse of the procedure of proving given above.)(e) $PRV(2^{O(n)})=L_{\overline{sat}}$.
$f$

$n$

$f$

$n$

$f$

$L_{\overline{sat}}$

Our main results in this section are:
Theorem 2. For any polynomial $d(n),$ $PRV(d(n))$ is NP-complete.

Theorem 3. If
andare polynomials such that $d_{1}(n)<d_{2}(n)$ for all $n\geq 1$ , then
$PRV(d_{2}(n))$ is better than $PRV(d_{1}(n))$ .
$d_{2}$$d_{1}$

Thus, for example, $PRV(n),$ $PRV(n+1),$$PRV(n+i),$
is an infinite sequence ofbetter NPC approximations of. For a set of predicates, let $PRV(d(n), L)$ denote the setof predicates such that can be reduced to some predicate in by the three operations (atmost $d(n)$ times for (i\"u)).
$\cdots$$\cdots,$$L_{\overline{\ell at}}$

$f$

$f$

$L$

$g$

$L$

Open Question. Does there exist a polynomial $d(n)$ such that for any NPC approxima$PRV(d(n), A)$ is a better NPC approximation than ?
tion of$A$$L_{\overline{sat}},$$A$

7
Proofs of Theorems 2 and 3 (Sketch).

4.

We first show a key lemma for both theorems. (Note that the property (e) of the previous section
is an old result in the field of switching theory. The following lemma demonstrates that there
is a predicate for which we need an exponential number of operations to get only one prime
implicant.)

Lemma 1. We can construct a predicate of clauses such that exactly $q(t)=\Theta(c^{t})$ (forsome $c>1$ ) apphcations of the duplication operations are needed to show its provability.
$f$

Proof. The predicate

$f$

$t$

consists of the following (1) to (3).

$U(n)(1,2)U(n-1)(\overline{1}, \overline{2})U(n-2)(3,4)U(n-3)(\overline{3}, \overline{4})\cdots U(2)(n-1, n)U(1)(\overline{n-1}, \overline{n})$(1)$V(n)(1, \overline{2})V(n-1)(\overline{1},2)V(n-2)(3, \overline{4})V(n-3)(\overline{3},4)\cdots V(2)(n-1,\overline{n})V(1)(\overline{n-1}, n)$(2)$W_{1}(n)(1, \overline{2})W_{1}(n-1)(\overline{1},2)W_{1}(n-2)(3,4)W_{1}(n-3)(\overline{3},\overline{4})\cdots W_{1}(2)(n-1, n)W_{1}(1)(\overline{n-1}, \overline{n})$$W_{2}(n)(1,2)W_{2}(n-1)(\overline{1}, \overline{2})W_{2}(n-2)(3, \overline{4})W_{2}(n-3)(\overline{3},4)\cdots W_{2}(2)(n-1,\overline{n})W_{2}(1)(\overline{n-1}, n)$$W_{3}(n-2)(3, \overline{4})W_{3}(n-3)(\overline{3},4)W_{3}(n-4)(5,6)W_{3}(n-5)(\overline{5}, \overline{6})\cdots W_{3}(2)(n-1, n)W_{3}(1)(\overline{n-1}, \overline{n})$$W_{4}(n-2)(3,4)W_{4}(n-3)(\overline{3}, \overline{4})W_{4}(n-4)(5,\overline{6})W_{4}(n-5)(\overline{5},6)\cdots W_{4}(2)(n-1, \overline{n})W_{4}(1)(\overline{n-1}, n)$$W_{n-3}(4)(n-3, \overline{n-2})W_{n-3}(3)(\overline{n-3}, n-2)W_{n-3}(2)(n-1, n)W_{n-3}(1)(\overline{n-1}, \overline{n})$$W_{n-2}(4)(n-3, n-2)W_{n-2}(3)(\overline{n-3},\overline{n-2})W_{n-2}(2)(n-1,\overline{n})W_{n-2}(1)(\overline{n-1}, n)$(3)where $U(i)(k, k+1)=(U(i)+z_{k})(U(i)+z_{k+1}),$ $U(i)(k, \overline{k+1})=(U(i)+z_{k})(U(i)+\overline{z_{k+1}})$ , and$U(n-1),$ $U(n)$ aresimilarly for $U(i)(\overline{k}, k+1)$ and. Furthermore, $U(1),$ $U(2),$$U(i)(\overline{k}, \overline{z_{k+1}})$$u_{1},$$\overline{u_{1}}+u_{2},$$\overline{u_{1}}+\overline{u_{2}}+\cdots+\overline{u_{(n-2)}}+u_{(n-1)},$$\cdots,$$\cdots,$$\overline{u_{1}}+\overline{u_{2}}+\cdots+\overline{u_{(n-2)}}+\overline{u_{(n-1)}}$, respectively.

Namely,(4)$(F+U(1))(F+U(2))\cdots(F+U(n))$

can be modified to. Variables$W_{j}(i)$$z_{1},$$F$(a sum of literals) by repeated merge operations. Similarly for $V(i)$ and$\cdots,$$z_{n}$are called main-variables and those in $U(i),$ $V(i)$ and$W_{j}(i)$are called

sub-variables.
We first show that is provable. Removing the sub-variables of (1) as above, we getclauses uf the following form
$f$$x_{1}+x_{2}+x_{3}+x_{4}+\cdots+x_{2i-1}+x_{2i}+\cdots+x_{n-1}+x_{n}$ ,$2^{n/2}$(5). It should be noted that we need an exponential
or
number of duplication operations in this process. Similarly we getones from (2) hke
where$(x_{2i-1}, x_{2i})=(\overline{z_{2:-1}}, z_{2};)$$(z_{2i-1}, \overline{z_{2i}})$$2^{n/2}$$y_{1}+y_{2}+y_{3}+y_{4}+\cdots+y_{2:-1}+y_{2i}+\cdots+y_{n-1}+y_{n}$ ,(6)

8where $(y_{2i-1}, y_{2i})=(z_{2i-1}, z_{2i})$ or
clauses like$(\overline{z_{2i-1}}, \overline{z_{2:}})$. Now, from the first line of (3), we can imply$z_{1}+z_{2}+x_{3}+x_{4}+\cdots+x_{n-1}+x_{n}$,$\overline{z_{1}}+\overline{z_{2}}+x_{3}+x_{4}+\cdots+x_{n-1}+x_{n}$,$2^{n/2}$

and(7)

where $x_{3}+x_{4}+\cdots+x_{n-1}+x_{n}$ is exactly the same as (5). Thus we can combine (5) and (7) to
imply all the predicates denoted by$x_{3}+x_{4}+\cdots+x_{n-1}+x_{n}$.

(8)Similarly, we can get(9)$y_{3}+y_{4}+\cdots+y_{n-1}+y_{n}$are removed
andfrom (6) and the second line of (3). Then using the third line of (3),andare removed from (9) using the forth line of (3). We can continue thisfrom (8). Also$x_{3}$$y_{3}$$x_{4}$$y_{4}$

procedure until both$x_{n-1}+x_{n}$andare implied, from which, as one can easily see,$y_{n}-\iota+y_{n}$$z_{n}\overline{z_{n}}$can be implied.

We shall next show that what we did above is the only possibility of proving . As an
easier case, suppose that (1) is replaced by $2^{n/2}-1$ clauses, say (1’), that consist of all the clauses
denoted by $x_{1}+x_{2}+\cdots+x_{n}$ except a single (any) one, which we denote by $z_{1}’+z_{2}’+\cdots+z_{n}’$ . Then
we can show that the set of clauses (1’), (2) and (3) is satisfiable: Set values tothenthen $z_{2i-1}=1,$ $z_{2i}=0$ . If
as follows: If$z_{2i-1}=0,$ $z_{2i}=1$ . Then all the other $2^{n/2}-1$ clauses then this $z_{1}’+z_{2}’+\cdots+z_{n}’$ clearly$f$$z_{1},$$(z_{2i-1}’, z_{2i}’)=(\overline{z_{2l-1}}, z_{2i})$$z_{2},$$\cdots,$$z_{n}$$(z_{2i-1}’, z_{2i}’)=(z_{2i-1}, \overline{z_{2i}})$become 1. In terms of (2), either $V(n)(1, \overline{2})=(V(n)+z_{1})(V(n)+\overline{z_{2}})$ or $V(n-1)(\overline{1},2)=$(V $(n-1)+\overline{z_{1}}$ ) $(V(n-1)+z_{2})$ becomes 1 by the above assignment regardless of the values ofthe sub-variables in $V(n)$ and $V(n-1)$ . Therefore, if for example the former is 1, then all theother clauses, $V(n-1)(\overline{1},2),$ $V(n-2)(3, \overline{4})$ , and so on can be made 1 by assigning proper values
only to the sub-variables in $V(n-1),$ $V(n-2)$ , and so on (namely, $v_{n-1}=v_{n-2}=\cdots=v_{1}=1$ ).
As for the first line of (3), either
or $W_{1}(n-1)(\overline{1},2)$ becomes 1 regardless of $W_{1}(n)$or $W_{1}(n-1)$ , and all the other clauses can be made 1 only by properly setting $W_{1}(n-2),$ .
Similarly for the second line (either $W_{2}(n-2)(3,\overline{4})$ or $W_{2}(n-3)(\overline{3},4)$ becomes 1) and for the
rest of (3).
$W_{1}(n)(1,\overline{2})$$\cdots$

This argument also holds for (2) and for each line of (3). Namely, if we try to delete subvariables before main-variables, we have to do so by expanding each line into all the possible. On the other hand, considering that sub-variables are able to be deleted only byclauses ofthe standard expansion, it turns out that to try to combine, say $U(n-2)(3,4)$ and $V(n-2)(3,\overline{4})$before deleting the sub-variables does not help to our goal. Therefore, if we could prove the$z_{i}’ s$9predicate using only a polynomial number of the duplication operation, it would be only by: (i)We first expand (completely) the last several (not too many) lines of (3). (ii) Then using thoseclauses not including sub-variables we try to delete main-variables of the rest of the lines before

deleting sub-variables. This, however, is impossible since the process intuitively means that wetry to delete main-variables fromtowards , which is the opposite direction compared to thesuccessful proof (but using exponential delete operations) described before. We omit the details
which need rather tedious case-analysis.
$z_{n}$$z_{1}$$\square$Lemma 2. There is a predicates of 5 clauses that is provable if we can use the duplication
operation once but is not provable only by (i) and (ii).
Proof The predicate shown in the example of Section 3 meets the condition

口

From these two lemmas, the following lemma is then implied:clausesLemma 3. For any polynomial $d(t)$ , we can construct a predicate of$d(t)$
apphcations of the duplication operation to show its provability.
such that we need exactly(Proof is omitted.)$f$$o(\iota^{1/2})$

Lemma 4 [7]. There is a polynomial-time reduction from 3-CNF predicates into CNF
predicates such thatis in $PRV(0)$ iff is satisfiable andincludes $O(t^{2})$ clauses if
has clauses. (Namely $PRV(0)$ is NP-complete.)$\alpha$$\alpha(f)$$f$$\alpha(f)$

$f$

$t$

Now it is not hard to complete the proof for Theorem 2. We design a similar reductoin
as Lemma 4: For a 3-CNF predicate
of clauses, we first set a sufficiently large number,
say $n=t^{3}$ . By Lemma 3, we then a predicate
such that exactly $d(n)$ duplication operations
are needed to imply a single literal, say . (This can be done by replacing each clause inof lemma 3 by $(A=\sigma).)g_{1}$ contains $O(t^{1.5})$ clauses. We then construct
such that we can$fromg_{2}$only by operations (i) and (ii) iff the 3-CNF predicate
imply tris satisfiable. Now thewhere is a trivial (satisfiable) predicate just to adjast the number
target predicate isof clauses of to . One can see that is in $PRV(d(n))$ iff go is satisfiable.
$t$$g_{0}$$g_{1}$$A$$\sigma$$f$$g_{2}$$g_{0}$$g$$g$$g_{1}g_{2}g_{3}$$n$$g_{3}$$g$

Theorem 3 is almost trivial by Lemma 3.

Acknowledgement. The author would like to thank Jose Balcazar for his suggestion of
possible extensions of P-levelability to the current form.

References[1] M. Abadi, E. Allender, A. Broader, J. Feigenbaum, and A. Hemachandra. On generating
solved instances of computational problems. In Proc. CRIPT88, 1988.
[2] J. Balcazar, J. Diaz, and J. Gabarro. Structural Complexity. Springer, 1989.

$\Pi$

10
[3] S. Ben-David, B. Chor, O Goldreich, and M. Luby. On the theory of average case complexity.
In Proc. $21stACM$ Symp. on Theory of Computing, pp. 204-216, 1989.
[4] S. Even, A. Selman, and Y. Yacobi. The complexity of promise problems with application
to pubhc-key cryptography. Information and Control, Vol. 61,, 1984.

[5] R. Impagliazzo and L. Levin. No better ways to generate hard np instances than picking
uniformly at random. In Proc. $31st$ IEEE Symp. on Foundations of Computer Science,

pp. 812-821, 1990.
[6] K. Iwama, H. Abeta, and E. Miyano. Random generation of satisfiable and unsatisfiable
CNF predicates. In Proc. 12th IFIP World Computer Congress, pp. 322-328, 1992.
[7] K. Iwama and E. Miyano. Security of test-case generation with known answers. In Proc.
AAAI Spring Symposium Series, 1993.
[8] B. Krishnamurthy. Constructing test cases for partitioning heuristics. IEEE Trans. Com-put., Vol. 36, pp. 1112-1114, 1987.
[9] D. Mitchell, B. Selman, and H. Levesque. Hard and easy distributions of SAT problems.

In Proc. Tenth National Conference on Artificial Intellegence, pp. 459-465, 1992.
[10] L. Sanchis. On the complexity of test case generation for NP-hard problems.
Process. Lett., Vol. 36, pp. 135-140, 1990.

Inform.

[11] L. Sanchis and M. Fulk. On the efficient generation of language instances. SIAM J. Comput.,Vol. 19, pp. 281-296, 1990.
[12] V. Shvatal and E. Szemeredi. Many hard examples for resolution. J. Assoc. Comput. Mach.,Vol. 35, pp. 759-768, 1988.
[13] G. Tinhofer. Generating graphs uniformly at random. In Computational graph theory,
pp. 235-255. Springer, 1990.