Chicago Journal of Theoretical Computer Science

The MIT Press

Volume 1999, Article 4 25 March 1999

ISSN 1073–0486. MIT Press Journals, Five Cambridge Center, Cambridge, MA 02142-1493 USA; (617)253-2889; journals-orders@mit.edu, journals-info@mit.edu. Published one article at a time in L^{A}TEX source form on the Internet. Pagination varies from copy to copy. For more information and other articles see:

• http://mitpress.mit.edu/CJTCS/

• http://www.cs.uchicago.edu/publications/cjtcs/

• ftp://mitpress.mit.edu/pub/CJTCS

• ftp://cs.uchicago.edu/pub/publications/cjtcs Karg, Köbler, and Schuler Complexity of Generating Test Instances (Info)

The Chicago Journal of Theoretical Computer Science is abstracted or indexed in Research Alert,◯^{R}SciSearch,◯^{R}Current Contents◯^{R}/Engineering Computing & Technology, and CompuMath Citation Index.◯^{R}

\begin{matrix}c \\ ◯ \end{matrix}1999 The Massachusetts Institute of Technology. Subscribers are licensed to use journal articles in a variety of ways, limited only as required to insure fair attribution to authors and the journal, and to prohibit use in a competing commercial product. See the journal’s World Wide Web site for further details. Address inquiries to the Subsidiary Rights Manager, MIT Press Journals; (617)253-2864; journals-rights@mit.edu.

The Chicago Journal of Theoretical Computer Science is a peer-reviewed scholarly journal in theoretical computer science. The journal is committed to providing a forum for significant results on theoretical aspects of all topics in computer science.

Editor-in-Chief: Janos Simon Consulting Editors: Joseph Halpern, Stuart A. Kurtz, Raimund Seidel Editors:

Martin Abadi  Greg Frederickson John Mitchell
Pankaj Agarwal Andrew Goldberg Ketan Mulmuley
Eric Allender Georg Gottlob Gil Neiger
Tetsuo Asano  Vassos Hadzilacos David Peleg
Laszló Babai  Juris Hartmanis Andrew Pitts
Eric Bach  Maurice Herlihy James Royer
Stephen Brookes Ted Herman  Alan Selman
Jin-Yi Cai  Stephen Homer  Nir Shavit
Anne Condon  Neil Immerman  Eva Tardos
Cynthia Dwork Howard Karloff  Sam Toueg
David Eppstein Philip Klein  Moshe Vardi
Ronald Fagin  Phokion Kolaitis Jennifer Welch
Lance Fortnow Stephen Mahaney Pierre Wolper
Steven Fortune Michael Merritt

Managing Editor: Michael J. O’Donnell

Electronic Mail: chicago-journal@cs.uchicago.edu

This paper is a contribution to a special issue on the 1996 Dagstuhl workshop on ”Structure and Complexity” by Eric Allender.

[ii]

The Complexity of Generating Test Instances^{∗}

Christoph Karg Johannes Köbler Rainer Schuler

25 March, 1999

Abstract

Recently, Watanabe proposed a framework for testing the correct-

Abstract-1

ness and average-case performance of algorithms that purport to solve a given NP search problem efficiently on average with respect to some distribution on the instances. The idea is to randomly generate certified instances under some distribution that resembles the input distribution. Watanabe showed that unless RE = NE, test instances cannot be generated for some NP search problems. We further discuss Watanabe’s approach and show, as an upper bound, that test instances can be generated for every NP search problem with non-adaptive queries to an NP oracle.

We also introduce Las Vegas and Monte Carlo types of test instance

Abstract-2

generators and show that these generators can be used to find out (with high confidence) whether an algorithm is correct and efficient on average. It is shown that Monte Carlo generators can be easily constructed for all RP search problems and that Las Vegas generators exist for all ZPP search problems as well as for other problems such as prime factorization. On the other hand, we prove that Monte Carlo generators can only exist for problems in NP ∩ co-AM.

1 Introduction

The class NP is one of the most intensively studied classes in computational

1-1

Karg, Köbler, and Schuler Complexity of Generating Test Instances §1

complexity theory, for it contains a large variety of problems that are of 1 practical importance. There are two types of problems that we are interested in, namely decision problems and search problems. Solving a decision problem means to decide whether a given instance has a solution, and solving a search problem means to actually find a solution. Although, at first glance, search problems seem more difficult to solve than decision problems, in many cases, they are equivalent under polynomial-time Turing reductions. For example, since any NP search problem is polynomial-time Turing reducible to any NP-complete (decision) problem, it follows that NP-complete problems have self-computable witnesses (in the sense of [BD76, Bal89]), meaning that solutions can be efficiently computed by asking oracle queries to the corresponding decision problem.

∗An extended abstract of the paper was presented at the Fourteenth Symposium on Theoretical Aspects of Computer Science (STACS), Springer-Verlag, Lecture Notes in Computer Science 1200, pp. 375–386, 1997.

Since polynomial-time algorithms do not exist for NP-complete problems

1-2

unless P = NP, it seems reasonable to look for algorithms that are efficient in the average case [Lev86] (see [Gur91] or [Wan97] for a survey). In practical applications, instances occur with certain probabilities. To model this process, we use probabilistic Turing machines that output instances in time polynomial in the length of the generated instances [BCGL92].

Besides designing efficient algorithms it is also important to find ways

1-3

of testing the correctness (and performance) of a given algorithm. Ideally, one would like to give a proof that the algorithm is correct and efficient. However, in some cases, a mathematical proof may be hard to obtain, or the proof may be long and complex. Thus, in practical terms, it is reasonable to test algorithms by feeding them with carefully chosen instances for which the solutions are already known. An obvious approach is to use a probabilistic polynomial-time bounded algorithm that generates instances of the problem together with some solution. To be useful, these test instances should be generated according to some distribution that resembles the frequencies with which the instances occur in practice.

In this paper our objective is to verify the “global correctness” of a given

1-4

algorithm A in the sense that, on a randomly selected input (according to the underlying distribution on the instances), the output of A is correct with high probability. This should be seen in contrast to the program checking approach in [BK95], where the outcome of the algorithm on a single instance has to be verified. Watanabe [Wat94] introduced a framework for globally checking the correctness and average-case behavior of algorithms. Intuitively, a generator for an NP search problem only needs to solve the problem on instances that are (randomly) generated by the generator itself, whereas an algorithm has to solve the problem on instances that are (randomly) gener-

2 ated “from outside.” Thus, for some NP search problems it might be easier to find a generator than to find an algorithm that solves it. For example, it is not hard to construct a test instance generator for prime factorization under the standard distribution (which is uniform on each input length). On the other hand, no efficient on-average algorithm is known that on input of a binary number n, either outputs a factor of n in case n is composite, or outputs “prime” otherwise. In fact, this is the basis for the practical security of, for example, the RSA cryptosystem. Also, for certain random self-reducible problems [TW87, AFK89] it is possible to generate instances (along with some solution) according to the distribution induced by the self-reduction. Examples are the quadratic residue and the discrete logarithm problems.

A test instance generator, as introduced by Watanabe, is a probabilistic

1-5

algorithm G that generates instances along with a solution; in particular, G only produces positive instances. Moreover, on input 0^{n}, G is required to output each positive instance of length n with sufficiently large probability (compared with the conditional distribution on the set of all positive instances of length n). As shown by Watanabe, there exist NP search problems for which test instances cannot be generated unless RE = NE. In fact, since for certain distributions the generator has to amplify the probability of the positive instances by an exponential factor, we can show that this is even true for very simple search problems.

In our model, a generator may produce positive as well as negative in-

1-6

stances. As in Watanabe’s approach, we require that the generator G output a witness along with every positively classified instance, i.e., G never misclassifies a negative instance. Moreover, each instance x has to be generated with a probability that is polynomially related to the probability μ(x) with which x occurs in practice. Thus, G is not required to amplify the probability of the positive instances. Furthermore, this condition implies that any algorithm is efficient on the generated instances if and only if it is efficient under the given distribution μ.

We define two types of test instance generators in this paper, namely,

1-7

a Monte Carlo generator and a Las Vegas generator. While a Monte Carlo generator is allowed to misclassify a (positive) instance with small probability, a Las Vegas generator has to classify all generated instances correctly. We show how these generators can be used to decide efficiently (and with high confidence) whether a given algorithm A for an NP search problem is correct with respect to μ. Further, we describe how to construct Monte Carlo generators for all RP search problems as well as Las Vegas generators for all

3 ZPP search problems.

In general, whereas logarithmically many adaptive queries are useless,

1-8

a polynomial number of non-adaptive queries to an NP set turn out to be sufficient to generate test instances for any NP search problem. This implies, in particular, that under the assumption NP = RP, any distributional NP search problem has a test instance generator.

Further, by an application of the universal hashing technique, we show

1-9

that the domain of any search problem for which a Monte Carlo generator exists (under the standard probability distribution) necessarily belongs to co-AM. Similarly, Las Vegas generators can only exist for NP search problems whose domain belongs to NP ∩ co-NP. As a consequence, Monte Carlo or Las Vegas generators do not exist for search problems with an NP-complete domain, unless the polynomial-time hierarchy collapses.

Finally, we define a reducibility between NP search problems that, similar

1-10

to the reducibility introduced by Levin [Lev86, BG93], preserves the probabilities of the instances. Via this reducibility we can obtain a test instance generator for a given NP search problem provided that we already have a test instance generator for some NP search problem to which the given one reduces.

2 Preliminaries

In this paper we use the standard notations and definitions of computa-

2-1

tional complexity theory (see, for example, [BDG95]). An introduction to the theory of computational average-case complexity can be found in [Gur91, BCGL92, Wan97]. Given below are some of the basic definitions we will use.

All languages considered here are over the alphabet Σ = {0, 1}. The

2-2

length of a string x ∈ Σ^{∗} is denoted by |x|. For a set A of strings, let A^{=n} = A ∩ Σ^{n} and A^{≤n} = ⋃_{k=0}^{n} A^{=k}. We denote the cardinality of a finite set A by ∥A∥, and we write A(x) = 1, if x ∈ A, and A(x) = 0 otherwise. The pairing function ⟨·, ·⟩ : Σ^{∗} × Σ^{∗} → Σ^{∗} is defined as ⟨x, y⟩ = d(x)01y, where d(x_{1} … x_{n}) = x_{1}x_{1} … x_{n}x_{n}. Note that ⟨x, y⟩ is computable and invertible in polynomial time, and for all x, y ∈ Σ^{∗}, |⟨x, y⟩| = 2|x| + |y| + 2.

Probability functions and distributions. Let μ be a probability

2-3

distribution on Σ^{∗}. Associated with μ are a probability function that we also denote by μ and a distribution function, denoted by μ^{∗}. More formally, μ and

4 μ^{∗} are functions from Σ^{∗} into the interval [0, 1] such that ∑_{x} μ(x) = 1 and μ^{∗}(x) = ∑_{y≤x} μ(y), where, as usual, ≤ denotes the lexicographic ordering on Σ^{∗}. For any set X ⊆ Σ^{∗} let μ(X) = ∑_{x∈X} μ(x). We refer to the distribution with the probability function μ_{st}(x) = 1/(|x|(|x| + 1)2^{|x|}) as the standard distribution.

Let μ, ν : Σ^{∗} → [0, 1] be functions. We say that μ is polynomially domi-

2-4

nated by ν (in symbols: μ ⪯ ν) [Lev86] if, for some polynomial p and all x, μ(x) ≤ p(|x|) · ν(x). In case μ ⪯ ν and ν ⪯ μ, the distributions μ and ν are called equivalent (in symbols: μ ≡ ν) [WB95]. A function f from Σ^{∗} to the non-negative integers is polynomial on μ-average [Lev86] if there exists a constant ϵ > 0 such that

∑_{x≠λ} \frac{f^{ϵ}(x)}{|x|} · μ(x) < ∞.

The set of functions that are polynomial on μ-average is closed under addition and multiplication. Furthermore, if μ is dominated by ν, then every function that is polynomial on ν-average is polynomial on μ-average [Lev86, Gur91].

A distribution is called p-computable if its distribution function μ^{∗} is

2-5

polynomial-time computable in the sense of Ko and Friedman [KF82], i.e., there exists a polynomial time bounded deterministic Turing transducer M such that, for all x and all k, it holds that |M(x, 1^{k}) − μ^{∗}(x)| ≤ 2^{−k}. A distribution is called samplable [BCGL92] if there exists a probabilistic Turing machine M that on input λ outputs x with probability μ(x). If, in addition, M is polynomial-time bounded in the length of the output, then μ is called p-samplable. It is easy to see that the standard distribution μ_{st} is p-computable. Furthermore, every p-computable distribution is dominated by some p-samplable distribution [BCGL92, Theorem 7].

Distributional NP search problems. An NP search problem is spec-

2-6

ified by a binary polynomial-time decidable witness relation R and a polynomial q_{R} such that R(x, w) implies |w| = q_{R}(|x|). Any w for which R(x, w) holds is called a solution (witness) for x. An instance x is called a positive instance in case it has a solution, and a negative instance, otherwise. We assume without loss of generality that λ is never a solution. A witness relation R also specifies an NP decision problem, namely D_{R} = {x ∈ Σ^{∗} | ∃w : R(x, w)}. D_{R} is also called the domain of R. In case D_{R} = Σ^{∗}, R is called a total NP search problem.

A distributional NP search problem is a pair (R, μ) consisting of a witness

2-7

relation R and a p-samplable probability function μ. A (deterministic) al-5 gorithm A efficiently solves (R, μ) if the running time of A is polynomial on μ-average and A computes a solution for all inputs x in the domain of R, whereas it outputs λ on all other inputs.

3 Generating Positive Test Instances

As pointed out in the introduction, the aim of test instance generation is to

3-1

verify the quality (correctness and performance) of a given algorithm. In this section we will discuss Watanabe’s approach to the test instance generation problem. Specifically, Watanabe requires the following properties of a test instance generator G for a distributional NP search problem (R, μ): G is a probabilistic polynomial-time algorithm, which, on input of 0^{n}, either outputs ⊥ (“not successful”) or generates some instance x of length n together with a solution w for x. Moreover, G has to output each positive instance with non-negligible probability compared with the conditional probability function ρ_{n} on the positive instances of length n. In particular, G is not allowed to output any negative instance, and hence, it is more appropriate to speak of G as a generator for the promised NP search problem restricted to the positive instances.

Definition 1 (Test Instance Generator [Wat94]) Let (R, μ) be a distributional NP search problem and let D be the domain of R. A probabilistic polynomial-time Turing machine G is called a test instance generator for (R, μ) if there is a polynomial q such that for all n,

1. on every path, G(0^{n}) outputs either ⊥ or a pair ⟨x, w⟩ such that R(x, w) and x ∈ Σ^{n}, and

2. if μ(D^{=n}) > 0, then for every x ∈ D^{=n}, G(0^{n}) outputs with probability at least ρ_{n}(x)/q(n) a pair of the form ⟨x, w⟩, w ∈ Σ^{∗}. Here, ρ_{n}(x) = μ(x)/μ(D^{=n}) is the probability of x under the condition that x belongs to D^{=n}.

As shown by Watanabe, generators of this type can be used to detect,

3-2

for a given input length n (in expected time polynomial in n and 1/ε), that an algorithm makes an error, provided that errors occur with probability ε (with respect to ρ_{n}). Furthermore, they can be used to find out that an algorithm is not efficient (with respect to ρ_{n}) [Wat94]. More precisely, if G

6 is a test instance generator for a search problem (R, μ), then the quality of a given algorithm A with respect to ρ_{n} can be verified as follows.

1. If A makes an error on strings of length n with probability at least ε, then with probability at least ε, A makes at least one error on a polynomial-size sample S generated by G, i.e., the test instances in S are obtained by running G(0^{n}) a polynomial number of times.

2. If A needs more than n^{k} steps on Σ^{n} with probability at least ε, then with probability at least ε, A needs more than n^{k} steps on some input from a polynomial-size sample S generated by G.

We note that, since in Definition 1 the probability that G(0^{n}) outputs ⟨x, w⟩ is not bounded from above, an algorithm A may take exponential time on average under the distribution induced by the generator even if A is polynomial on ρ-average. In fact, it may happen that G produces with high probability instances that have probability zero with respect to ρ.

The following result, due to Watanabe, shows that it is unlikely that there

3-3

exists a test instance generator for every distributional NP search problem.

Theorem 1 ([Wat94]) If every NP search problem has a test instance generator under the standard distribution, then RE = NE.

In fact, the proof shows that randomly computing instance/witness pairs for all NP search problems with a tally domain is impossible, unless RE = NE. Similarly, it can be seen that there are total NP search problems (i.e., with domain Σ^{∗}) that do not have test instance generators under the standard distribution, unless NE∩co-NE ⊆ RE. This shows that generating test instances for an NP search problem for which decision is easy might nevertheless be hard.

We now show that generating test instances in Watanabe’s model may be

3-4

impossible even for trivial search problems since, for some distributions, it is necessary to amplify the probability of the positive instances of fixed length by an exponential factor.

Theorem 2 Let R = {⟨x, 1⟩ | x ∈ Σ^{∗} − {1}^{∗}}. If for every p-samplable distribution μ there exists a test instance generator for (R, μ), then RE = NE.

Proof of Theorem 2 Since RE = NE if and only if NP ∩ TALLY ⊆ RP

Proof of Theorem 2-1

[Boo74], it suffices to show that the assumption implies that every tally NP 7 set T is contained in RP. Let R_{T} be a binary relation and p be a polynomial such that for all n, 0^{n} ∈ T if and only if there exists a string w ∈ Σ^{p(n)} with R_{T} (0^{n}, w).

Now consider the p-samplable distribution μ generated by the following

Proof of Theorem 2-2

probabilistic algorithm:

First, guess a positive integer n with probability proportional to n^{−2}. Then, uniformly guess a string w ∈ Σ^{p(n)} and output w in case R_{T} (0^{n}, w) holds; else, output 1^{p(n)}.

Then any test instance generator G for (R, μ) has the property that, if 0^{n} ∈ T, then either R_{T} (0^{n}, 1^{p(n)}) holds or G(0^{p(n)}) outputs with probability 1/n^{O(1)} a pair ⟨w, 1⟩ for which R_{T} (0^{n}, w) holds. Note that, in the latter case, ρ_{p(n)}{w ∈ Σ^{p(n)} | R_{T} (0^{n}, w)} = 1.

Proof of Theorem 2 □

An interesting question is whether the converse of Theorem 1 (or of The-

3-5

orem 2) is also true. As shown below, non-adaptive queries to an NP set are sufficient to generate test instances for any distributional NP search problem. This implies in particular that under the assumption NP = RP, any distributional NP search problem has a test instance generator.

As shown in the following proposition, O(log n) many queries to any oracle

3-6

are not helpful for a generator in Watanabe’s model.

Proposition 1 If, for a distributional NP search problem (R, μ), test instances can be generated with O(log n) queries to some oracle, then there exists a test instance generator for (R, μ).

Proof of Proposition 1 Let M be a probabilistic oracle Turing machine that generates test instances by asking O(log n) queries to some oracle. Let M′ simulate M where each oracle query is answered by a fair coin toss. If M outputs a pair ⟨x, w⟩, then M′ outputs ⟨x, w⟩ only if R(x, w) holds, and outputs ⊥ otherwise. Then the probability that all oracle answers are guessed correctly is 1/n^{O(1)}, implying that M′ still fulfills the conditions of Definition 1.

Proof of Proposition 1 □

8 The upper bound on the complexity of generating test instances that we

3-7

will give in Theorem 3 below is based on the universal hashing technique [CW79, Sip83, VV86]. Let H_{m,k} be the class of all linear hash functions from Σ^{m} to Σ^{k}. The following lemma is straightforward (cf. [Pap94]).

Lemma 1 Let S be a subset of Σ^{m} of cardinality ∥S∥ = s such that 2^{k} ≤ 3s ≤ 2^{k+1} and let x ∈ S. Then, for a uniformly chosen hash function h from H_{m,k}, it holds with probability at least 2/(9s) that x is the only element in S with h(x) = 0^{k}. Hence, with probability at least 2/9, there exists a unique x ∈ S with h(x) = 0^{k}.

Proof of Lemma 1 Since H_{m,k} is a universal class of hash functions, it follows for a uniformly chosen h that Prob[h(x) = 0^{k}] = 2^{−k} and that

Prob[h(x) = 0^{k} ∧ ∃y ∈ S − {x} : h(y) = 0^{k}]
≤ ∑_{y∈S−{x}} Prob[h(x) = 0^{k} ∧ h(y) = 0^{k}] < s2^{−2k}.

Consequently, the probability that x is the only pre-image of 0^{k} in S can be calculated as follows.

Prob[h(x) = 0^{k} ∧ ∀y ∈ S − {x} : h(y) ≠ 0^{k}]
= Prob[h(x) = 0^{k}] − Prob[h(x) = 0^{k} ∧ ∃y ∈ S − {x} : h(y) = 0^{k}]
> 2^{−k}(1 − s2^{−k})
≥ 2/(9s), since s2^{−k}(1 − s2^{−k}) ≥ 2/9 for 1/3 ≤ s2^{−k} ≤ 2/3.

Proof of Lemma 1 □

Theorem 3 For every distributional NP search problem (R, μ), test instances can be generated with parallel queries to some set in NP.

Proof of Theorem 3 Let D be the domain of R and let q be a polynomial such that |w| = q(|x|) for all solutions w for x. Let M be a probabilistic Turing machine witnessing that μ is p-samplable and let p be a polynomial time bound for M, i.e., the time used by M(λ) to output a string x is bounded by p(|x|). For any string r ∈ Σ^{p(n)}, let M_{r}(λ) denote the output of M (if any) when using sequence r as random source. The test instance generator G for (R_{D}, μ) is defined as follows.

9 On input 0^{n}, G first guesses two integers k ∈ {1, …, p(n) + 1}, l ∈ {1, …, q(n) + 1} and two linear hash functions h_{1} ∈ H_{p(n),k}, h_{2} ∈ H_{q(n),l}. By asking in parallel the queries y_{i} = ⟨0^{n}, i, h_{1}, h_{2}⟩, 1 ≤ i ≤ m = 2p(n) + q(n) + 2, to the oracle A, G obtains a sequence s = A(y_{1}) … A(y_{m}) of oracle answer bits. Then G determines strings r ∈ Σ^{p(n)}, w ∈ Σ^{q(n)}, and x ∈ Σ^{∗} such that ⟨r, w⟩ = s and x = M_{r}(λ). Finally, if |x| = n and R(x, w) hold, then G outputs the pair ⟨x, w⟩; otherwise, G outputs the symbol ⊥.

For every x, let S_{x} = {r ∈ Σ^{p(|x|)} | M_{r}(λ) = x} denote the set of all random sequences r using which M outputs x, and let S_{n} = ⋃_{x∈D^{=n}} S_{x}. For every r ∈ S_{n} let α_{r} denote the probability that G(0^{n}) guesses integers k, l and linear hash functions h_{1}, h_{2} such that r is the only string in S_{n} with h_{1}(r) = 0^{k} and there exists a unique solution w for M_{r}(λ) with h_{2}(w) = 0^{l}. Then it follows by Lemma 1 that

α_{r} ≥ \frac{1}{(p(n) + 1)(q(n) + 1)} · \frac{2}{9 · ∥S_{n}∥} · \frac{2}{9}.

Now consider the following NP oracle set A defined as

⟨0^{n}, i, h_{1}, h_{2}⟩ ∈ A ⇔ ∃⟨r, w⟩ : h_{1}(r) = 0^{k}, r ∈ S_{n}, h_{2}(w) = 0^{l},
R(M_{r}(λ), w), and the ith bit of ⟨r, w⟩ is 1.

Then it follows that, for every x ∈ D^{=n}, G(0^{n}) outputs a pair of the form ⟨x, w⟩, w ∈ Σ^{∗}, with probability at least

∑_{r∈S_{x}} α_{r} ≥ \frac{4 ∥S_{x}∥}{81(p(n) + 1)(q(n) + 1) ∥S_{n}∥} = \frac{4}{81(p(n) + 1)(q(n) + 1)} · ρ_{n}(x).

Proof of Theorem 3 □

We end this section by observing that the above theorem can easily be extended to the Monte Carlo type of generators that we will introduce in the next section.

10

4 Test Instance Generation Without Amplification

In this section we propose a slightly different model of generating test in-

4-1

stances. As explained above, our aim is to verify the quality of a given algorithm but to avoid the need for amplifying the probability of the positive instances by a possibly exponential factor. This goal is achieved by allowing the generator not only to output pairs ⟨x, w⟩, where x is a positive instance and w is a solution for x, but also to output pairs of the form ⟨x, λ⟩, where x might be negative as well. (Recall our assumption that λ is not a solution for any instance.) In the definition of a Monte Carlo generator, we also allow that positive instances x be generated (with small probability) in the form ⟨x, λ⟩, whereas this is totally forbidden for a Las Vegas generator. Before we proceed to the formal definition of these generators, let us explain why it might be easier to generate test instances for a distributional NP search problem than to solve the problem itself.

Intuitively, a generator for a distributional NP search problem can benefit

4-2

from the advantage that it may intertwine the process of randomly generating an instance with the process of constructing a suitable solution. In contrast, an algorithm has to solve the problem on instances that are randomly generated “from outside.” Thus, there might exist distributional NP search problems for which it is easier to generate instance/witness pairs than to solve the problem. In fact, this phenomenon is exploited in the design of many cryptographic protocols, such as in generating public keys together with some (secret) trapdoor information. For example, the security of the RSA cryptosystem is based on the practical hardness of the factorization problem, i.e., no efficient-on-average algorithm is known (under the standard distribution) that on input of n outputs a factor of n in case n is composite, and outputs “prime” otherwise. On the other hand, it is computationally easy to randomly generate composite numbers together with some factor. Indeed, it is not hard to construct a Las Vegas generator for the corresponding search problem (see Proposition 4).

Next we define the notion of an instance generator for a distributional

4-3

NP search problem (R, μ). An instance generator G efficiently generates instances in accordance with the distribution μ. Furthermore, it provides, along with each generated instance x, either some solution w (implying that x belongs to the domain of R) or the empty string λ (implying absolutely

11 nothing on the membership status of x). In fact, an instance generator may only output pairs of the form ⟨x, λ⟩. In order to force G to generate “good” test instances, we will later impose an additional bound on the probability that G outputs a pair ⟨x, λ⟩ when x is positive.

Definition 2 (instance generator) Let (R, μ) be a distributional NP search problem. A probabilistic Turing machine G (with output but with no input) is called an instance generator for R under μ if

1. on every halting computation, G outputs a pair ⟨x, w⟩ with the property that either R(x, w) holds or w = λ,

2. the time needed by G to output a pair of the form ⟨x, w⟩, w ∈ Σ^{∗}, is polynomially bounded in |x|, and

3. μ_{G} is equivalent to μ, where μ_{G}(x) is the probability that G generates instance x, i.e., μ_{G}(x) = ∑_{w∈Σ^{∗}} μ_{G}(x, w), where μ_{G}(x, w) is the probability that G outputs the pair ⟨x, w⟩.

Note that if G were required to stop on all paths, then only finitely many instances could be generated. Actually, we allow that μ_{G}(Σ^{∗}) < 1, i.e., G might run forever with positive probability. Also, if μ(Σ^{n}) = 1/n^{O(1)}, then G can easily be modified to produce instances of a given length according to the conditional probability of that length. (This is similar to Watanabe’s model, but note that the generator might still output negative instances.)

Suppose that G is an instance generator for a distributional NP search

4-4

problem (R, μ) and let A be an algorithm. Since the distributions μ and μ_{G} are equivalent, the running time of A is polynomial on μ-average if and only if it is polynomial on μ_{G}-average [Lev86].

We distinguish between two types of generators, depending on the quality

4-5

of the generated test instances. A Monte Carlo generator is allowed to err with small probability, whereas a Las Vegas generator only generates test instances that are correctly classified.

Definition 3 (Monte Carlo generator) Let G be an instance generator for a distributional NP search problem (R, μ) with domain D.

1. G is called a Monte Carlo generator for R under μ if for every polynomial q,

μ_{G}(x, λ) ≤ \frac{μ_{G}(x)}{q(|x|)}

12

holds for all but finitely many instances x in D.

2. G is called a Las Vegas generator for R under μ if G never outputs a pair ⟨x, λ⟩ with x ∈ D.

We note that if μ(D^{=n}) = 1/n^{O(1)}, then any Monte Carlo generator for

4-6

(R, μ) can be transformed into a test instance generator for (R, μ) according to Watanabe’s model.

We next show how a Monte Carlo generator can be used to find out

4-7

efficiently and with high confidence whether a given algorithm A for a distributional NP search problem (R, μ) is correct with respect to the underlying probability distribution μ. Without loss of generality, we can assume that A makes only errors on instances in the domain D of R. More formally, for any subset D′ of D, we call the probability μ{x ∈ D′ | A(x) = λ} that x ∈ D′ and A does not find a witness for x the error rate of A on D′. We say that a pair ⟨x, w⟩ convicts A on D′ if R(x, w) and x ∈ D′ hold, but A(x) = λ.

Theorem 4 Let G be a Monte Carlo generator for a distributional NP search problem (R, μ) and let D be the domain of R. Then there exists a polynomialtime probabilistic transducer T such that the following statements hold for any search algorithm A.

• If the error rate of A on D^{≤l} is at least 1/m, then for all n, T on input ⟨1^{n}, 1^{m}, 1^{l}⟩ produces with probability at least 1−2^{−n} a sequence of pairs, at least one of which convicts A on D^{≤l}.

• If additionally, A is polynomial on μ-average then for some polynomial t, the sequence contains with probability at least 1 − 2^{−n} a pair ⟨x, w⟩ that convicts A on D^{≤l} and for which A(x) stops after at most t(l, m) steps.

Proof of Theorem 4 Let G be a Monte Carlo generator for (R, μ) and

Proof of Theorem 4-1

let q be a polynomial such that |w| = q(|x|) for all solutions w of x. By Definition 2(3), there is a polynomial p such that for all instances x,

μ(x)/p(|x|) ≤ μ_{G}(x) ≤ p(|x|) · μ(x).

Since Definition 3(1) guarantees that for all but finitely many x ∈ D, μ_{G}(x, λ) ≤ μ_{G}(x)/2, we can assume that, for all instances x ∈ D,

∑_{w∈Σ^{q(|x|)}} μ_{G}(x, w) ≥ μ_{G}(x)/2 ≥ μ(x)/(2p(|x|)).

13 Since the error rate of A on D^{≤l} is at least 1/m, it follows that G outputs with probability at least 1/(2mp(l)) a pair ⟨x, w⟩ with x ∈ D^{≤l} and A(x) = λ. Therefore, during 2mnp(l) independent computations, G will output with probability at least 1−(1−1/(2mp(l)))^{2mnp(l)} > 1−2^{−n} some pair ⟨x, w⟩ with x ∈ D^{≤l} and A(x) = λ. Note that since the running time of G is polynomially bounded in the length of the output, T can suspend the simulation of G after a polynomial number (in l) of steps.

Note that since μ and μ_{G} are equivalent, the assumption that A is poly-

Proof of Theorem 4-2

nomial on μ-average implies that A is polynomial on μ_{G}-average, i.e., there exist constants k, c > 0 such that ∑_{x≠λ} \frac{time_{A}(x)^{1/k}}{|x|} · μ(x) < c, where time_{A}(x) denotes the running time of A on input x. Hence, it follows that

μ_{G}{x ∈ D^{≤l} | A(x) runs for more than t(l, m) steps} ≤ 1/(4mp(l)),

where t is the polynomial t(l, m) = (2cmlp(l))^{k}. This implies that G outputs with probability at least 1/(4mp(l)) a pair ⟨x, w⟩ that convicts A on D^{≤l} and for which A(x) stops after at most t(l, m) steps.

Proof of Theorem 4 □

It is interesting to note that the assumption in the above theorem can be

4-8

weakened for certain distributions μ. In fact, if μ has the property that for some polynomial q and all n,

∑_{x:|x|>q(n)} μ(x) ≤ 1/n,

and if the error rate of A on D (instead of D^{≤l} as in the above theorem) is at least 1/m, then it follows that μ{x ∈ D^{≤q(2m)} | A(x) = λ} ≥ 1/(2m). Hence, letting T′(1^{n}, 1^{m}) = T (1^{n}, 1^{2m}, 1^{q(2m)}), the above theorem implies that with probability at least 1 − 2^{−n}, T′(1^{n}, 1^{m}) produces an instance x ∈ D^{≤q(2m)} with A(x) = λ.

Next we consider distributional RP search problems (R, μ) (meaning that

4-9

the binary relation R witnesses that its domain D_{R} belongs to RP, i.e., each x ∈ D_{R} has at least 2^{q_{R}(|x|)−1} many solutions). As shown below, instance/witness pairs for (R, μ) can be easily generated by sampling a string x according to μ and randomly generating a witness for x.

Proposition 2 For every distributional RP search problem (R, μ) there exists a Monte Carlo generator.

14 Proof of Proposition 2 Let D be the domain of R and let q be a polynomial such that |w| = q(|x|) for all solutions w of x. Let M be a probabilistic Turing machine witnessing that μ is p-samplable. Consider the following instance generator G for (R, μ).

Simulate M. In case M outputs an instance x, |x| = n, guess randomly and independently a sequence w_{1}, …, w_{n} of strings of length q(n) and determine the lexicographically largest string w in the set {λ} ∪ {w_{i} | 1 ≤ i ≤ n and R(x, w_{i}) holds}. Output the pair ⟨x, w⟩.

It is easy to verify that G is a Monte Carlo test instance generator for (R, μ).

Proof of Proposition 2 □

As shown in the next theorem, it is unlikely that every NP search problem

4-10

has a Monte Carlo generator under the standard probability distribution. In fact, Monte Carlo generators can only exist if the domain of the search problem belongs to co-AM. As a consequence, Monte Carlo generators do not exist for NP search problems with an NP-complete domain unless the polynomial-time hierarchy collapses to the second level [BHZ87, Sch88]. For definitions of the class AM and of Arthur-Merlin games we refer the reader to [BM88] or to a textbook, such as [BDG90] or [KST93].

Theorem 5 If there exists a Monte Carlo generator for an NP search problem R under the standard distribution, then the domain of R is contained in co-AM.

Proof of Theorem 5 Let G be a Monte Carlo generator for (R, μ_{st}) and

Proof of Theorem 5-1

let p be a polynomial bounding the running time of G. From Definition 2(3), we can conclude that, for some polynomial s,

\frac{1}{s(|x|)2^{|x|}} ≤ μ_{G}(x) ≤ \frac{s(|x|)}{2^{|x|}}.

From Definition 3(1), we know that, for any polynomial q,

μ_{G}(x, λ) ≤ \frac{μ_{G}(x)}{q(|x|)}

holds for all but finitely many x in the domain D of R. Now let S_{x} be the set of strings r ∈ Σ^{p(n)} such that G outputs the pair ⟨x, λ⟩ when using r as

15 random source. Let q(n) be the polynomial 2^{5}s(n)^{2}. Then, for all but finitely many x, the following implications are true (where n = |x|).

\begin{aligned}x ∈ D & ⇒ & μ_{G}(x, λ) ≤ \frac{s(n)}{2^{n}q(n)} & ⇒ & ∥S_{x}∥ ≤ \frac{s(n)2^{p(n)}}{2^{n}q(n)} & ⇒ & ∥S_{x}∥ ≤ \frac{2^{p(n)−n−5}}{s(n)} , \\ x ∉ D & ⇒ & μ_{G}(x, λ) ≥ \frac{1}{s(n)2^{n}} & ⇒ & ∥S_{x}∥ ≥ \frac{2^{p(n)}}{s(n)2^{n}} & ⇒ & ∥S_{x}∥ ≥ \frac{2^{p(n)−n}}{s(n)} . \end{aligned}

Therefore, letting k(n) = p(n) − n − ⌈log_{2} s(n)⌉ − 2, it follows, for all but finitely many x ∈ D, that ∥S_{x}∥ ≤ 2^{k(n)−2} and for all but finitely many x ∉ D, that ∥S_{x}∥ ≥ 2^{k(n)+2}.

Now consider for a fixed instance x (for which the above implications are

Proof of Theorem 5-2

true) the random variable Z that for a uniformly chosen h in H_{p(n),k(n)} gives the number of strings r ∈ S_{x} for which h(r) = 0^{k(n)}. Then the expectation of Z is E(Z) = 2^{−k(n)} ∥S_{x}∥ and the variance is V (Z) = 2^{−k(n)}(1−2^{−k(n)}) ∥S_{x}∥ < E(Z) [VV86]. Thus, by using Chebyshev’s inequality it follows that

x ∈ D ⇒ Prob[Z ≥ 1] ≤ E(Z) ≤ 1/4,
x ∉ D ⇒ Prob[Z = 0] ≤ Prob[|Z − E(Z)| ≥ E(Z)] ≤ V (Z)/E(Z)^{2} < 1/E(Z) ≤ 1/4.

The Arthur-Merlin protocol for \overline{D} proceeds as follows: On input x, |x| = n, Arthur randomly chooses a hash function h ∈ H_{p(n),k(n)} and asks Merlin to show him a string r ∈ S_{x} with h(r) = 0^{k(n)}. Since Merlin succeeds with probability at least 3/4, if x ∉ D, and with probability at most 1/4, otherwise, it follows that \overline{D} ∈ AM.

Proof of Theorem 5 □

It is interesting to note that the above proof can easily be extended to any

4-11

NP search problem (R, μ), where μ is positive and 1/μ(x) can be polynomially approximated by an FP function f(x), i.e., for some constant c and all x, f(x) ≤ 1/μ(x) ≤ f(x) · |x|^{c}.

By combining Theorem 5 with the result that NP is not contained in

4-12

co-AM unless the polynomial-time hierarchy collapses to the second level [BHZ87, Sch88], we obtain the following corollary.

Corollary 1 If there exists a Monte Carlo generator for some distributional NP search problem (R, μ_{st}) whose domain is NP-complete, then PH = Σ_{2}^{P}.

16 We end this section by considering the Las Vegas type of generators.

4-13

Define a ZPP search problem to be a RP search problem whose domain is in ZPP. Then a Las Vegas generator can be constructed for any ZPP search problem in a similar way as in the proof of Proposition 2.

Proposition 3 For every distributional ZPP search problem there exists a Las Vegas generator.

It is also interesting to observe that some search problems that are not

4-14

known to be efficiently solvable have a Las Vegas generator. As an example, we consider the prime factorization problem under the standard distribution μ_{st}. We assume that numbers are given in binary, i.e., the string x is used to describe the number (denoted by n_{x}) with the binary representation 1x. More precisely, let R_{prime} denote the witness relation defined as

R_{prime}(x, w) = \begin{cases}1, & n_{w} is a prime factor of n_{x} and n_{w} < n_{x}, \\ 0, & otherwise. \end{cases}

Proposition 4 There exists a Las Vegas generator for the prime factorization problem (R_{prime}, μ_{st}).

Proof of Proposition 4-1 Proof of Proposition 4 Recall that the domain of R_{prime} belongs to ZPP [AH87], i.e., there is a probabilistic polynomial-time algorithm A that on input of x either accepts (implying that n_{x} is prime) or rejects (implying that n_{x} is composite) or outputs “?” (with probability at most 1/2). Furthermore, since the standard distribution μ_{st} is equivalent to some p-samplable distribution, there is a probabilistic Turing machine M that on input λ outputs x with probability μ_{M}(x), where μ_{st}(x)/4 ≤ μ_{M}(x) ≤ 4μ_{st}(x) (cf. [BCGL92, Theorem 7]).

Now consider the following generator G:

Proof of Proposition 4-2

With probability 1/2, execute step (1) or step (2).

(1) Choose randomly under μ_{M} a string x in Σ^{∗}. If A(x) accepts, then output ⟨x, λ⟩. Otherwise, loop forever.

(2) Choose randomly and independently under μ_{M} two strings y, w ∈ Σ^{∗}. If A(w) accepts and if y ≠ λ, then output ⟨x, w⟩, where 1x is the binary representation of n_{y} · n_{w}. Otherwise, loop forever.

17 It is easy to see that G fulfills conditions (1) and (2) of Definition 2 as well as condition (2) of Definition 3. Furthermore, it is not hard to verify that the distribution μ_{G} induced by G is equivalent to μ_{st} (i.e., G also fulfills Definition 2(3)), implying that G is a Las Vegas generator for (R_{prime}, μ_{st}).

Proof of Proposition 4 □

On the other hand, Las Vegas generators can only exist for NP search

4-15

problems whose domain belongs to NP ∩ co-NP.

Proposition 5 If there exists a Las Vegas generator for an NP search problem R under the standard distribution μ_{st}, then the domain of R is contained in co-NP.

Proof of Proposition 5 Let D be the domain of a search problem R and let G be a Las Vegas generator for (R, μ_{st}) whose running time is bounded by some polynomial s. We show that \overline{D} ∈ NP. Consider the following NP machine M:

On input x, simulate G for at most s(|⟨x, λ⟩|) steps and accept if G outputs the pair ⟨x, λ⟩.

Since μ_{st}(x) > 0 for all x and since G is a Las Vegas generator for (R, μ_{st}), M accepts x if and only if x ∈ \overline{D}.

Proof of Proposition 5 □

Corollary 2 If there exists a Las Vegas generator for some distributional NP search problem (R, μ_{st}) whose domain is NP-complete, then NP = co-NP.

As a final remark, it is not hard to see that, for every set L that has

4-16

self-computable witnesses (in the sense of [BD76, Bal89]), there is a Las Vegas generator using L as an oracle. For example, since graph isomorphism (GI) and graph automorphism (GA) have self-computable witnesses and non-adaptively self-computable witnesses, respectively (cf. [Sch76] and [LT93, Lemmas 5.2 and 5.3]), there exist Las Vegas generators for the corresponding search problems that ask adaptive (non-adaptive) queries to GI (GA, respectively).

18

5 Hard Problems for Test Instance Generation

In this section we consider the question of how the test instance generation

5-1

problem for one NP search problem (S, ν) can be reduced to the test instance generation problem for another NP search problem (R, μ). Inspired by [Wat94], we provide a way to transform a Monte Carlo or Las Vegas generator for (S, ν) to a generator for any problem (R, μ) that reduces to (S, ν) via the following kind of reduction.

Definition 4 Let (R, μ) and (S, ν) be distributional NP search problems. Let D_{R} (D_{S}) be the domain of R (S, respectively). Then (R, μ) is generator reducible to (S, ν) if there exist functions f, g ∈ FP and polynomials p, q such that:

1. For all y and r, if f(y, r) ≠ ⊥, then f(y, r) ∈ D_{R} if and only if y ∈ D_{S}.

2. For all y, v, and r, if f(y, r) ≠ ⊥ and S(y, v), then R(f(y, r), g(y, v, r)).

3. f is honest, i.e., for all y, r, if f(y, r) ≠ ⊥ then p(|f(y, r)|) ≥ |y|.

4. μ is equivalent to ϕ, where ϕ is the distribution induced by ν, q, and f, i.e., ϕ(x) = ∑_{y,r} ν(y)2^{−|r|}, where the sum ranges over all strings y, r such that |r| = q(|y|) and f(y, r) = x.

Two distributional NP search problems are called generator equivalent if they are generator reducible to each other.

In the sequel, we assume without loss of generality that f(y, rr′) = f(y, r)

5-2

for all y, r, r′ such that |r| = q(|y|), and that g(y, λ, r) = λ for all y, r.

Proposition 6 If (R, μ) is generator reducible to (S, ν) and if there exists a Monte Carlo (Las Vegas) generator for (S, ν), then there exists a Monte Carlo (Las Vegas, respectively) generator for (R, μ).

Proof of Proposition 6 Assume that (R, μ) reduces to (S, ν) via the func-

Proof of Proposition 6-1

tions f, g and the polynomials p, q. Let G be a generator for (S, ν). Consider the following algorithm G′.

Simulate G. If G produces a pair ⟨y, v⟩, then randomly guess a string r ∈ {0, 1}^{q(|y|)}. If f(y, r) ≠ ⊥, then output the pair ⟨f(y, r), g(y, v, r)⟩; otherwise, loop forever.

19 We claim that G′ is an instance generator for (R, μ) (of the same type as G). By Definition 4 we know that if G′ outputs ⟨x, w⟩, then either R(x, w) or w = λ. Let C(x) = {(y, r) | f(y, r) = x, |r| = q(|y|)} and let t and t′ be polynomials such that μ_{G}(x) ≥ ν(x)/t(|x|) and ϕ(x) ≥ μ(x)/t′(|x|), where ϕ is the distribution induced by f, q, and ν. Then we have, for all x,

μ_{G′}(x) = ∑_{(y,r)∈C(x)} μ_{G}(y) 2^{−|r|}

≥ ∑_{(y,r)∈C(x)} \frac{1}{t(|y|)}ν(y) 2^{−|r|}

≥ \frac{1}{t(p(|x|))} \underbrace{∑_{(y,r)∈C(x)} ν(y) 2^{−|r|}}_{ϕ(x)}

≥ \frac{1}{t(p(|x|)) t′(|x|)}μ(x).

Thus, μ ⪯ μ_{G′}, and since μ_{G′} ⪯ μ can be derived in a similar way, μ_{G′} ≡ μ follows. Furthermore, since f is honest, the time needed by G′ to output a pair ⟨x, w⟩ is polynomially bounded in |x|.

Assume now that G is a Monte Carlo generator for (S, ν). We have to

Proof of Proposition 6-2

show that for any polynomial t and almost all x ∈ D_{R}, μ_{G′}(x) ≥ t(|x|) · μ_{G′}(x, λ). Let s be a polynomial such that |f(y, r)| ≤ s(|y|) for all y and r, |r| = q(|y|). Since G is a Monte Carlo generator, it holds for almost all y ∈ D_{S} that μ_{G}(y) ≥ t(s(|y|)) · μ_{G}(y, λ). Then, for all sufficiently large x ∈ D_{R} it follows that

μ_{G′}(x) = ∑_{(y,r)∈C(x)} μ_{G}(y) 2^{−|r|}

≥ ∑_{(y,r)∈C(x)} t(s(|y|)) μ_{G}(y, λ) 2^{−|r|}

≥ t(|x|) ∑_{(y,r)∈C(x)} μ_{G}(y, λ) 2^{−|r|}

= t(|x|) · μ_{G′}(x, λ).

Thus, it follows that G′ is a Monte Carlo generator for (R, μ).

In the case that G is a Las Vegas generator for (S, ν), it follows imme-

Proof of Proposition 6-3

diately from the properties of f and g that G′ is a Las Vegas generator for 20 (R, μ).

Proof of Proposition 6 □

Another important property of the generator reducibility is transitivity.

Proposition 7 The generator reducibility is transitive.

Proof of Proposition 7 Let (R_{i}, μ_{i}), i = 1, 2, 3, be distributional NP search problems. Let D_{i} be the domain of R_{i}, i = 1, 2, 3. Assume that (R_{i}, μ_{i}) is generator reducible to (R_{i+1}, μ_{i+1}) via the functions f_{i}, g_{i} ∈ FP and the polynomials p_{i}, q_{i}, i = 1, 2. Consider the functions f and g defined as

f(y, r_{1}, r_{2}) = \begin{cases}f_{1}(f_{2}(y, r_{2}), r_{1}), & f_{2}(y, r_{2}) ≠ ⊥, \\ ⊥, & otherwise. \end{cases}

and

g(y, v, r_{1}, r_{2}) = \begin{cases}g_{1}(f_{2}(y, r_{2}), g_{2}(y, v, r_{2}), r_{1}), & R_{3}(y, v), f(y, r_{1}, r_{2}) ≠ ⊥, \\ λ, & otherwise. \end{cases}

Since f_{1} and f_{2} satisfy the conditions of Definition 4, it follows that f and g fulfill the following conditions for all y, r_{1}, r_{2} with f(y, r_{1}, r_{2}) ≠ ⊥.

1. y ∈ D_{3} ⇔ f_{2}(y, r_{2}) ∈ D_{2} ⇔ \underbrace{f_{1}(f_{2}(y, r_{2}), r_{1})}_{f(y,r_{1},r_{2})} ∈ D_{1},

2. \begin{aligned}R_{3}(y, v) & ⇒ & R_{2}(f_{2}(y, r_{2}), g_{2}(y, v, r_{2})) \\ & ⇒ & R_{1}(\underbrace{f_{1}(f_{2}(y, r_{2}), r_{1})}_{f(y,r_{2}r_{1})}, \underbrace{g_{1}(f_{2}(y, r_{2}), g_{2}(y, v, r_{2}), r_{1})}_{g(y,v,r_{2}r_{1})}), \end{aligned}

3. |y| ≤ p_{2}(p_{1}(|f_{1}(f_{2}(y, r_{2}), r_{1})|)) ≤ p_{2}(|f_{2}(y, r_{2})|), and

4. μ_{1} ≡ ϕ(x), where ϕ is the distribution induced by f, q, and μ_{3}. Indeed, since |f_{2}(y, r_{2})| is polynomially bounded in |y|, there exists a polynomial q such that q_{2}(|y|) + q_{1}(|f_{2}(y, r_{2})|) ≤ q(|y|) for all y, r_{2} with f_{2}(y, r_{2}) ≠ ⊥. For a given x, consider the following sets:

A(x) = {(y, r_{1}, r_{2}) | f(y, r_{1}, r_{2}) = x, |r_{2}| = q_{2}(|y|), |r_{1}| = q(|y|) − q_{2}(|y|)},
B(x) = {(y, r_{1}, r_{2}) | f(y, r_{1}, r_{2}) = x, |r_{2}| = q_{2}(|y|), |r_{1}| = q_{1}(|f_{2}(y, r_{2})|)},
C_{1}(x) = {(z, r_{1}) | f_{1}(z, r_{1}) = x, |r_{1}| = q_{1}(|z|)},
C_{2}(z) = {(y, r_{2}) | f_{2}(y, r_{2}) = z, |r_{2}| = q_{2}(|y|)}.

21 For i = 1, 2, let ϕ_{i} be the distribution induced by f_{i}, q_{i}, and μ_{i+1}. Since

μ_{i} ≡ ϕ_{i}, it follows that
ϕ(x) = ∑_{(y,r_{1},r_{2})∈A(x)} μ_{3}(y)2^{−|r_{1}r_{2}|}

= ∑_{(y,r_{1},r_{2})∈B(x)} μ_{3}(y)2^{−|r_{1}r_{2}|}

= ∑_{(z,r_{1})∈C_{1}(x)} 2^{−|r_{1}|} · \underbrace{∑_{(y,r_{2})∈C_{2}(z)} μ_{3}(y)2^{−|r_{2}|}}_{ϕ_{2}(z)}

≥ ∑_{(z,r_{1})∈C_{1}(x)} 2^{−|r_{1}|} \frac{1}{p(|z|)}μ_{2}(z) (since μ_{2} ≡ ϕ_{2})

≥ \frac{1}{p′(|x|)} \underbrace{∑_{(z,r_{1})∈C_{1}(x)} 2^{−|r_{1}|}μ_{2}(z)}_{ϕ_{1}(x)} (since f_{1} is honest)

≥ \frac{1}{p′′(|x|)}μ_{1}(x) (since μ_{1} ≡ ϕ_{1}),

where p, p′ and p′′ are appropriately chosen polynomials. Thus, we have μ_{1} ⪯ ϕ, and since ϕ ⪯ μ_{1} can be shown similarly, it follows that μ_{1} ≡ ϕ.

Using the properties derived above it is easy to see that (R_{1}, μ_{1}) is generator reducible to (R_{3}, μ_{3}) via the functions f̂, ĝ, where

f̂(y, r) = \begin{cases}f(y, λ, r), & |r| < q_{2}(|y|), \\ f(y, r_{1}, r_{2}), & r = r_{1}r_{2}, |r_{2}| = q_{2}(|y|). \end{cases}

and ĝ is defined analogously.

Proof of Proposition 7 □

Next we present two problems from group theory that are generator equivalent. For this we need some notions from elementary group theory. For a more detailed introduction to group theory, we refer to [Hum96, Cam95]. Our reductions are based on the ones given in [Hof82].

22 S_{n} denotes the symmetric group of {1, …, n}, i.e. the set of all permu-

5-3

tations over {1, …, n}. For a set A ⊆ S_{n}, we denote by ⟨A⟩ the smallest subgroup of S_{n} that contains A. A is called a generator set for ⟨A⟩. It is known that every subgroup of S_{n} can be generated by a set of at most n − 1 permutations [Jer82].

Double Coset Membership (DCM, μ_{DCM})

Instance. Positive integer n (given in unary), sets A, B ⊆ S_{n} such that 1 ≤ ∥A∥ , ∥B∥ ≤ n − 1 and permutations π, ψ ∈ S_{n}.

Question. Do there exist α ∈ ⟨A⟩, β ∈ ⟨B⟩ such that ψ = απβ?

Distribution. Randomly and independently choose a positive integer n (with probability \frac{1}{n(n+1)}); then guess randomly and independently two integers a, b ∈ {1, …, n − 1} under uniform distribution. Guess randomly and uniformly a + b + 2 permutations from S_{n}. The density function is

μ_{DCM}(1^{n}, A, B, π, ψ) = \frac{1}{n(n + 1) (n − 1)^{2} (n!)^{∥A∥+∥B∥+2}} .

Group Factorization (GF, μ_{GF})

Instance. Positive integer n (given in unary), sets A, B ⊆ S_{n} such that 1 ≤ ∥A∥ , ∥B∥ ≤ n − 1 and a permutation ψ ∈ S_{n}.

Question. Do there exist α ∈ ⟨A⟩, β ∈ ⟨B⟩ such that ψ = αβ?

Distribution. Randomly and independently choose a positive integer n as above; then guess randomly and independently two integers a, b ∈ {1, …, n − 1} under uniform distribution. Guess randomly and uniformly a + b + 1 permutations from S_{n}. The density function is

μ_{GF}(1^{n}, A, B, ψ) = \frac{1}{n(n + 1) (n − 1)^{2} (n!)^{∥A∥+∥B∥+1}} .

Let R_{DCM} (R_{GF}) denote the search problem of DCM (GF, respectively).

Proposition 8 (R_{DCM}, μ_{DCM}) and (R_{GF}, μ_{GF}) are generator equivalent.

23 Proof of Proposition 8 We first show that (R_{GF}, μ_{GF}) is generator re-

Proof of Proposition 8-1

ducible to (R_{DCM}, μ_{DCM}). Since this reduction makes no use of the random bits, we omit the parameter r. For any instance ⟨1^{n}, A, B, π, ψ⟩ of DCM and potential solution ⟨α, β⟩, the reduction (f, g) is defined as

f(1^{n}, A, B, π, ψ) = ⟨1^{n}, π^{−1}Aπ, B, π^{−1}ψ⟩
g(⟨1^{n}, A, B, π, ψ⟩, ⟨α, β⟩) = \begin{cases}(π^{−1}απ, β) & α ∈ ⟨A⟩, β ∈ ⟨B⟩, ψ = απβ, \\ λ & otherwise. \end{cases}

Since for a given set A of permutations and a given permutation α it can be decided in polynomial time whether α belongs to ⟨A⟩ (see, for example, [Hof82]), it is easy to verify that this is indeed a generator reduction from (R_{GF}, μ_{GF}) to (R_{DCM}, μ_{DCM}). In fact, the density function induced by f and μ_{DCM} coincides with μ_{GF}.

Next we argue that (R_{DCM}, μ_{DCM}) is generator reducible to (R_{GF}, μ_{GF}).

Proof of Proposition 8-2

For any instance ⟨1^{n}, A, B, ψ⟩ of GF and potential solution ⟨α, β⟩, the reduction (f, g) is defined as

f(⟨1^{n}, A, B, ψ⟩, r) = \begin{cases}⟨1^{n}, A, π^{−1}Bπ, π, ψπ⟩, & r describes a π ∈ S_{n}, \\ ⊥, & otherwise, \end{cases}

g(⟨1^{n}, A, B, ψ⟩, ⟨α, β⟩, r) = \begin{cases}⟨α, π^{−1}βπ⟩, & α ∈ ⟨A⟩, β ∈ ⟨B⟩, ψ = αβ, \\ & r describes a π ∈ S_{n}, \\ λ, & otherwise. \end{cases}

Again, it is easy to verify that this is indeed a generator reduction. We remark that the density function induced by f and μ_{GF} is equal to μ_{DCM}.

Proof of Proposition 8 □

Finally, we show the existence of a hard problem in the sense that every

5-5

distributional NP search problem (R, μ) is generator reducible to it, provided the distribution μ is p-computable and the probabilities μ(x) are not too small.

Bounded Halting Problem (K, μ_{K})

Instance. A nondeterministic Turing machine M, a binary string x, and a

positive integer k, given in unary. 24 Question. Does M accept x within k steps?

Distribution. Randomly and independently guess M, x and k under standard distribution, i.e., the density function μ_{K} is

μ_{K}(M, x, 1^{k}) = \frac{1}{|M|(|M| + 1) 2^{|M|} |x|(|x| + 1) 2^{|x|} k(k + 1)}.

The definition of the search problem R_{K} is straightforward: R_{K}(⟨M, x, 1^{k}⟩, v) holds if and only if v describes an accepting computation of M on input x of length ≤ k.

Theorem 6 Let R be an NP search problem and let μ be a p-computable distribution such that for some polynomial p and all x, μ(x) ≥ 2^{−p(|x|)}. Then (R, μ) is generator reducible to (R_{K}, μ_{K}).

Proof of Theorem 6 Let (R, μ) be a distributional NP search problem

Proof of Theorem 6-1

such that μ is p-computable. Let D be the domain of R.

It is known [Lev86, Gur91, WB95] that D is many-one reducible to K

Proof of Theorem 6-2

via a function h ∈ FP that is one-one, length increasing, polynomial-time invertible and for which μ(x) and μ_{K}(h(x)) are equivalent. Let f be an FP function such that h(f(y)) = y for all y ∈ range(h). Furthermore, it is possible to compute in polynomial time from a given witness v for h(x) some witness w for x, i.e., there exists a function g ∈ FP such that R(x, g(h(x), v)) holds for every x, v with R_{K}(h(x), v). Thus, for every y ∈ range(h), the following statements hold.

1. f(y) ∈ D ⇔ y ∈ K,

2. R_{K}(y, v) ⇒ R(f(y), g(y, v)),

3. p(|f(y)|) ≥ |y| (since h(f(y)) = y), and

4. μ(x) is polynomially related to ∑_{y,f(y)=x} μ_{K}(y).

This implies that (R, μ) generator reduces to (R_{K}, μ_{K}) via f̂ and ĝ, where

f̂(y, r) = \begin{cases}f(y) & y ∈ range(h) \\ ⊥ & otherwise \end{cases}

and ĝ is defined analogously.

Proof of Theorem 6 □

Karg, Köbler, and Schuler Complexity of Generating Test Instances (Ref)

25 Remark. In the proof of Theorem 6 we used the completeness of the bounded halting problem for the class DistNP consisting of all pairs (L, μ) such that L is in NP and μ is p-computable [Lev86, Gur91]. In fact, the proof also works for other DistNP-complete problems such as the tiling problem, Post’s correspondence problem, the word problem for Thue systems and groups, and LR(k) testing of context-free grammars [Lev86, Gur91, WB95, Wan95, Kar97].

On the other hand, it remains open whether Theorem 6 can be extended

5-7

to p-samplable distributions μ. Note that there exists a similar open problem in average-case theory, namely, whether every distributional NP problem with a p-samplable distribution many-one reduces to the bounded halting problem [BG95]. Interestingly, under randomized truth-table reductions, every distributional NP (decision and search) problem with a p-samplable distribution reduces to the bounded halting problem [IL90, BCGL92].

Acknowledgments

We would like to thank the anonymous referees for helpful comments.

Acknowledgment of support: Christoph Karg’s work was supported by the Deutsche Forschungsgemeinschaft, Research Grant Schö 302/4-2.

References

[AFK89] M. Abadi, J. Feigenbaum, and J. Kilian. On hiding information from an oracle. Journal of Computer and System Sciences, 39:21– 30, 1989.

[AH87] L. Adleman and M. Huang. Recognizing primes in random polynomial time. In Proceedings of the 19th ACM Symposium on Theory of Computing, pages 462–469, New York, 1987. ACM Press.

[Bal89] J. L. Balcázar. Self-reducibility structures and solutions of NP problems. In Revista Matematica, volume 2, No. 2/3, pages 175– 184. Universidad Complutense de Madrid, Madrid, 1989.

26 [BCGL92] S. Ben-David, B. Chor, O. Goldreich, and M. Luby. On the theory

of average case complexity. Journal of Computer and System Sciences, 44:193–219, 1992.

[BD76] A. Borodin and A. Demers. Some comments on functional selfreducibility and the NP hierarchy. Technical Report 76-284, Department of Computer Science, Cornell University, 1976.

[BDG90] J. L. Balcázar, J. Díaz, and J. Gabarró. Structural Complexity II. EATCS Monographs on Theoretical Computer Science. Springer-Verlag, Berlin, 1990.

[BDG95] J. L. Balcázar, J. Díaz, and J. Gabarró. Structural Complexity I. EATCS Monographs on Theoretical Computer Science. Springer-Verlag, Berlin, second edition, 1995.

[BG93] A. Blass and Y. Gurevich. Randomized reductions of search problems. SIAM Journal of Computing, 22:949–975, 1993.

[BG95] A. Blass and Y. Gurevich. Matrix transformation is complete for the average case. SIAM Journal on Computing, 24(1):3–29, 1995.

[BHZ87] R. Boppana, J. Hastad, and S. Zachos. Does co-NP have short interactive proofs? Information Processing Letters, 25:27–32, 1987.

[BK95] M. Blum and S. Kannan. Designing programs to check their work. Journal of the ACM, 42(1):269–291, 1995.

[BM88] L. Babai and S. Moran. Arthur-merlin games: a randomized proof system and a hierarchy of complexity classes. Journal of Computer and System Sciences, 36:254–276, 1988.

[Boo74] R. Book. Tally languages and complexity classes. Information and Control, 26:186–193, 1974.

[Cam95] P. J. Cameron. Permutation groups. In R. Graham, M. Grötschel, and L. Lovász, editors, Handbook Of Combinatorics, chapter 12, pages 611–645. Elsevier, Amsterdam, 1995.

[CW79] J. L. Carter and M. N. Wegman. Universal classes of hash functions. Journal of Computer and System Sciences, 18:143–154, 1979.

27 [Gur91] Y. Gurevich. Average case completeness. Journal of Computer

and System Sciences, 42(3):346–398, 1991.

[Hof82] C. M. Hoffmann. Group-Theoretic Algorithms and Graph Isomorphism, volume 136 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, 1982.

[Hum96] J. F. Humphreys. A Course in Group Theory. Oxford Science Publications, Oxford, 1996.

[IL90] R. Impagliazzo and L. A. Levin. No better ways to generate hard NP-instances than picking uniformly at random. In Proceedings of the 31st IEEE Symposium on the Foundations of Computer Science, pages 812–821, Los Alamitos, CA, 1990. IEEE Computer Society Press.

[Jer82] M. Jerrum. A compact representation for permutation groups. In Proceedings of the 23rd IEEE Symposium on the Foundations of Computer Science, pages 126–133, Los Alamitos, CA, 1982. IEEE Computer Society Press.

[Kar97] C. Karg. LR(k) testing is average-case complete. In Proceedings of the 12th Annual IEEE Conference on Computational Complexity, pages 74–80, Los Alamitos, CA, 1997. IEEE Computer Society Press.

[KF82] K.-I. Ko and H. Friedman. Computational complexity of real functions. Theoretical Computer Science, 20:323–352, 1982.

[KST93] J. Köbler, U. Schöning, and J. Torán. The Graph Isomorphism Problem: Its Structural Complexity. Birkhäuser, Boston, 1993.

[Lev86] L. Levin. Average case complete problems. SIAM Journal on Computing, 15:285–286, 1986.

[LT93] A. Lozano and J. Torán. On the nonuniform complexity of the graph isomorphism problem. In K. Ambos-Spies, S. Homer, and U. Schöning, editors, Complexity Theory, Current Research, pages 1–45. Cambridge University Press, Cambridge, 1993.

28 [Pap94] C. Papadimitriou. Computational Complexity. Addison-Wesley,

Reading, MA, 1994.

[Sch76] C. Schnorr. Optimal algorithms for self-transformable problems. In Proceedings of the 3rd International Colloquium on Automata, Languages, and Programming, pages 322–337, Edinburgh, 1976. Edinburgh University Press.

[Sch88] U. Schöning. Graph isomorphism is in the low hierarchy. Journal of Computer and System Sciences, 37:312–323, 1988.

[Sip83] M. Sipser. A complexity theoretic approach to randomness. In Proceedings of the 15th ACM Symposium on Theory of Computing, pages 330–335, New York, 1983. ACM Press.

[TW87] W. Tompa and H. Woll. Random self-reducibility and zeroknowledge interactive proofs of possession of information. In Proceedings of the 28th IEEE Symposium on the Foundations of Computer Science, pages 472–482, Los Alamitos, CA, 1987. IEEE Computer Society Press.

[VV86] L. Valiant and V. Vazirani. NP is as easy as detecting unique solutions. Theoretical Computer Science, 47:85–93, 1986.

[Wan95] J. Wang. Average-case completeness of a word problem for groups. In Proceedings of the 27th ACM Symposium on Theory of Computing, pages 325–334, New York, 1995. ACM Press.

[Wan97] J. Wang. Average-case computational complexity theory. In L. A. Hemaspaandra and A. L. Selman, editors, Complexity Theory Retrospective 2, pages 295–328. Springer-Verlag, Berlin, 1997.

[Wat94] O. Watanabe. Test instance generation for promised NP search problems. In Proceedings of the 9th Structure in Complexity Theory Conference, pages 205–216, Los Alamitos, CA, 1994. IEEE Computer Society Press.

[WB95] J. Wang and J. Belanger. On the NP-isomorphism problem with respect to random instances. Journal of Computer and System Sciences, 50:151–164, 1995.

29