Chicago Journal of Theoretical Computer Science

The MIT Press

Volume 1999, Article 2 24 February 1999

ISSN 1073–0486. MIT Press Journals, Five Cambridge Center, Cambridge, MA 02142-1493 USA; (617)253-2889; journals-orders@mit.edu, journalsinfo@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 Wang Randomized Reductions (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 ensure 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

[ii] Wang Randomized Reductions (Info)

This article is included in the Special Issue on Computational Complexity containing articles based on selected presentations made at the Dagstuhl-Seminar Structure and Complexity, held September 30—October 4, 1996, at Schloß Dagstuhl, Germany. This special issue was edited by Eric Allender.

[iii]

Randomized Reductions and Isomorphisms

Jie Wang

24 February, 1999

Abstract

Randomizing reductions have provided new techniques for tackling average-case complexity problems. For example, although some NP-complete problems with uniform distributions on instances cannot be complete under deterministic one-one reductions [WB95], they are complete under randomized reductions [VL88]. We study randomized reductions in this paper on reductions that are one-one and honest mappings over certain input domains. These are reasonable assumptions since all the randomized reductions in the literature that are used in proving average-case completeness results possess this property. We consider whether randomized reductions can be inverted efficiently. This gives rise to the issue of randomized isomorphisms. By generalizing the notion of isomorphisms under deterministic reductions, we define what it means for two distributional problems to be isomorphic under randomized reductions. We then show a randomized version of the Cantor-Bernstein-Myhill theorem, which provides a sufficient condition for two distributional problems to be isomorphic under randomized reductions. Based on that condition we show that all the known average-case NP-complete problems (including those that are complete under deterministic reductions) are indeed isomorphic to each other under randomized reductions.

1 Introduction

Average-case complexity has attracted increasing attention recently. A ma-

1-1

jor objective of this study is to identify (standard, worst-case) NP-complete problems that are difficult, on average, from those that are easy, on average.

Wang Randomized Reductions §1

1 Various notions of reductions for distributional problems are useful tools for studying average-case complexity. A distributional problem is a pair consisting of a problem A and a probability distribution μ on instances of A. If A is an NP problem, then we call (A, μ) a distributional NP problem. Deterministic reductions are simpler and easier to use; they have been used to prove that some NP-complete problems under plausible distributions are averagecase complete. However, deterministic reductions have certain limitations. For example, under the assumption that EXP ≠ NEXP, distributional NP problems with flat distributions cannot be complete under deterministic reductions [Gur91]; and (without any assumption) distributional NP problems with flat distributions cannot be complete under deterministic one-one reductions [WB95]. Randomized reductions were introduced to overcome these limitations [VL88]. Some NP problems with flat distributions have been shown to be complete under randomized reductions [VL88, Gur91, BG95]. Randomized reductions have also been used to obtain several other interesting results. For example, using randomized reductions, Impagliazzo and Levin [IL90] showed that any NP search problem under any polynomial-time samplable distribution is reducible to some NP search problem under a uniform distribution. This result is also true for NP decision problems under randomized truth-table reductions [BDCGL92, Wan97]. Also, using randomized reductions, Belanger and Wang [BW97] showed that no NP problems over ranking of distributions are harder than over uniform distributions.

Gurevich [Gur91] and Blass and Gurevich [BG93, BG95] have conducted

1-2

intensive studies on randomized reductions. Through their work, we have gained deeper understandings on randomized reductions. We carry on this study a step further by considering reductions that are one-one and honest mappings over certain input domains. (A mapping f is honest if for any input x, the length of its image f(x) cannot be too short; namely, there is a polynomial p such that for any input x, p(|f(x)|) ≥ |x|.) These are reasonable assumptions since all the randomized reductions in the literature that are used in proving average-case completeness results possess this property. Moreover, we consider whether these reductions can be “inverted” efficiently. This gives rise naturally to the issue of randomized isomorphisms of averagecase NP-complete problems.

Berman and Hartmanis [BH77] were the first to study isomorphisms of

1-3

complete sets for resource-bounded worst-case complexity classes. They defined a notion of isomorphism under deterministic polynomial-time reductions. They showed that all the known NP-complete sets are polynomially

2 isomorphic, and they conjectured that it should also be true for all NPcomplete sets. This conjecture implies that P is different from NP. Although this conjecture has not been solved, it has stimulated a host of papers in structural complexity theory. Wang and Belanger [WB95] observed that some standard NP-complete problems, while isomorphic on the worst case, are not isomorphic on the average case under commonly used distributions. On the other hand, all the average-case NP-complete problems may still be isomorphic. To extend the isomorphism theory of Berman and Hartmanis from worst case to average case, Wang and Belanger [WB95] defined a notion of isomorphisms for distributional problems under deterministic reductions — a natural generalization of Berman and Hartmanis’ notion of isomorphisms. They showed that all the known average-case NP-complete problems that are complete under deterministic reductions are indeed isomorphic.

We consider whether the notion of isomorphisms can be further extended

1-4

to include randomized reductions, and we devote this paper to answering this question. We provide an affirmative answer: By generalizing the notion of isomorphisms under deterministic reductions, we define in a natural way what it means for two distributional problems to be isomorphic under randomized reductions. We then show a randomized version of the Cantor-Bernstein-Myhill theorem, which provides a sufficient condition for two distributional problems to be isomorphic under randomized reductions. Based on that condition we show that all the known average-case NP-complete problems (including those that are complete under deterministic reductions) are indeed isomorphic to each other under randomized reductions.

2 Average Time and Instance Distributions

We provide in this section basic definitions and results of average-case com-

2-1

plexity. For a recent survey of average-case complexity, its motivations, traps and escapes, the reader is referred to [Gur91, Wan97].

Let Σ = {0, 1}. We assume that all languages are subsets of Σ^{∗}. Let μ

2-2

denote a probability distribution (distribution, in short) over Σ^{∗}; i.e., μ is a real-valued function from Σ^{∗} to [0,1] such that ∑_{x} μ(x) = 1. The probability distributions we consider are on instances of computational problems. If a binary string does not encode an instance of the underlying problem, then that string has zero probability. The distribution function of μ, denoted by μ^{∗}, is defined by μ^{∗}(x) = ∑_{y≤x} μ(y), where ≤ is the standard lexicographical

3 order on Σ^{∗}. For a function f, we use f^{ε}(x) to denote (f(x))^{ε} for ε > 0 and we use f^{−1} to denote the inverse of f. We use IN to denote the natural numbers. We will consider decision problems in this paper; we will omit the word “decision” when there is no confusion.

Levin [Lev86] suggested to use multi-median time to measure average

2-3

computation time, and he gave the following definition.

Definition 1 ([Lev86]) A function f : Σ^{+} → IN is polynomial on μ-average if there is an ε > 0 such that ∑_{x} f^{ε}(x)|x|^{−1}μ(x) < ∞.

This notion of average time is robust and machine independent.

2-4

Let AP denote the class of all distributional problems (A, μ) such that A

2-5

can be solved by a deterministic algorithm whose running time is polynomial on μ-average. AP is an average-case analogue of P.

In what follows, we will use “p-time” to denote “polynomial-time,” and

2-6

“ap-time” to denote “average-polynomial-time.”

Let μ and ν be two distributions; then μ is dominated by ν, denoted by

2-7

μ ⪯^{p} ν, if there is a polynomial p such that for all x, μ(x) ≤ p(|x|)ν(x). A real-valued function r : Σ^{∗} → [0, 1] is p-time computable if there exists

2-8

a deterministic algorithm A such that for every string x and every positive integer k, A outputs a finite binary fraction y such that |r(x) − y| ≤ 2^{−k} and the running time of A is polynomially bounded in |x| and k [Ko83]. Clearly, if μ^{∗} is p-time computable, then so is μ; but Blass showed that the converse is not true unless P = NP (see [Gur91]). With this fact in mind, we assume throughout that when we say that μ is p-time computable, both μ and μ^{∗} are p-time computable.

Levin (see [Joh84]) hypothesized that any natural distribution μ is either

2-9

p-time computable or is dominated by a distribution that is. Strong evidence that supports this hypothesis is the fact that all the commonly used discrete distributions do satisfy this hypothesis. It is often natural to consider uniform distributions. We say that a distribution μ is uniform if μ is p-time computable and, for all x, μ(x) = ρ(|x|)2^{−|x|}, where ∑_{n} ρ(n) = 1 and there exists a polynomial p such that for all but finitely many n, ρ(n) ≥ 1/p(n). Levin [Lev86] used n^{−2} for ρ(n) for notational convenience (normalized by dividing by ∑_{n} n^{−2} = π^{2}/6), and |x|^{−2}2^{−|x|} is often referred to as the default uniform distribution. If an instance X consists of several parameters (x_{1}, x_{2}, …, x_{k}), then by uniform distribution of X we mean that each parameter x_{i} is selected independently and uniformly with respect to the default uniform distribution on x_{i}.

Wang Randomized Reductions §3.1

4 Let DistNP denote the class of distributional problems (A, μ) such that

2-10

A ∈ NP and μ is either p-time computable or is dominated by a distribution that is. By Levin’s hypothesis, DistNP includes all natural distributional NP problems. DistNP is a distributional analogue of NP.

3 Deterministic and Randomized Reductions

Several NP-complete problems under uniform distributions have been shown

3-1

to be in AP (e.g., see [Joh84, GS87]). To find out whether there are complete problems for DistNP, Levin [Lev86] defined and used the notion of polynomial-time many–one reducibility. Gurevich [Gur91] conducted a thorough investigation on this notion.

3.1 Deterministic Reductions

3-1.1 Let f be a function from Σ^{∗} to Σ^{∗}. Write f(ν)(y) to denote ∑_{f(x)=y} ν(x). Then f induces a distribution f(ν) on Σ^{∗} for the outputs of f. We say that μ is dominated by ν with respect to f, denoted by μ ⪯_{f}^{p} ν, if there exists a distribution μ_{1} such that μ is dominated by μ_{1} and, for all y ∈ range(f), ν(y) = f(μ_{1})(y).

Definition 2 ([Lev86, Gur91]) Let (A, μ_{A}) and (B, μ_{B}) be two distributional problems. Then (A, μ_{A}) is p-time many–one reducible to (B, μ_{B}), denoted by (A, μ_{A}) ≤_{m}^{p} (B, μ_{B}), if there exists a p-time computable reduction f such that A is many–one reducible to B via f and μ_{A} ⪯_{f}^{p} μ_{B}.

Polynomial-time many–one reductions have the desired properties

3.1-2

[Gur91]: If (A, μ_{A}) ≤_{m}^{p} (B, μ_{B}) and (B, μ_{B}) ∈ AP, then (A, μ_{A}) ∈ AP; polynomial-time many–one reductions are transitive.

The requirements of p-time many–one reductions can be weakened in two

3.1-3

ways without losing the two desired properties [Lev86, Gur91].

First, we may require only that the reduction be computable in time

3.1-4

polynomial on μ_{A}-average.

Second, we may use the following weaker domination condition. Dis-

3.1-5

tribution μ is weakly dominated by μ_{1}, denoted by μ ⪯^{ap} μ_{1}, if for all x, μ(x) ≤ h(x)μ_{1}(x), where h is polynomial on μ-average. Distribution μ is

5 weakly dominated by ν with respect to f, written as μ ⪯_{f}^{ap} ν, if there exists a distribution μ_{1} such that μ is weakly dominated by μ_{1} and ν(y) = f(μ_{1})(y) for all y ∈ range(f). Reductions defined under these two weaker requirements are called ap-time many–one reductions.

A distributional problem is many–one complete for DistNP (or sim-

3.1-6

ply average-case NP-complete) if it is in DistNP and every other problem in DistNP is ≤_{m}^{p}-reducible to it. Several distributional NP problems under uniform distributions have been shown to be many–one complete for DistNP [Lev86, Gur91, WB95, Wan95].

3.2 Randomized Reductions

The notion of many-one reductions has certain limitations. In particular, it is

3.2-1

not suitable for studying completeness of problems when “flat” distributions are presented. A distribution μ is flat [Gur91] if there exists an ϵ > 0 such that for all x, μ(x) ≤ 2^{−|x|^{ϵ}}. Uniform distributions for graph problems often turn out to be flat [Gur91, WB95]. Gurevich [Gur87, Gur91] showed that, unless nondeterministic exponential time collapses to deterministic exponential time, no distributional problems with flat distributions can be complete under ap-time many–one reductions. Wang and Belanger [WB95] further showed that, without any assumption, a distributional problem with a flat distribution cannot be complete under ap-time, one-one, and p-honest reductions.

We explain why deterministic reductions would fail: When instances of

3.2-2

the target problem are under a flat distribution, each instance of approximately the same length will have approximately the same weight, and this weight is too small to dominate the input distribution. So no matter how an instance of the target problem is selected by an honest deterministic reduction, the domination property will always be violated.

Venkatesan and Levin [VL88] showed that by using randomized reduc-

3.2-3

tions, one can overcome the difficulties caused by flat distributions. A randomized reduction is a standard randomized (probabilistic) algorithm that transforms one string to another. In [VL88], the purpose of using a randomized reduction is to generate instances of the target problem with sufficiently large probability. The idea is to supply a random source S_{x} for a reduction f from (A, μ_{A}) to (B, μ_{B}) on each instance x of A, such that different random strings s ∈ S_{x} will produce different instances f(x, s), and for all s ∈ S_{x}, x ∈ A if and only if f(x, s) ∈ B. Thus, although for each individual

6 instance f(x, s) of B, μ_{B}(f(x, s)) may be too small to dominate μ_{A}(x), the summation ∑_{s} μ_{B}(f(x, s)) may be large enough to meet the domination requirement for distributions. To make this point clearer, let us consider the following special case. Let S = { (x, s) : s ∈ S_{x} } and for all s ∈ S_{x}, |s| ≥ |x|. Assume that the reduction f is one-one on S and, for all x, ∑_{s∈S_{x}} 2^{−|s|} = 1. For a particular s ∈ S_{x}, μ_{B}(f(x, s)) may be too small to dominate μ_{A}(x), but ∑_{s∈S_{x}} μ_{B}(f(x, s)) = μ_{B}(f(x, s))2^{|s|} may well be large enough to dominate μ_{A}(x). Thus, if μ_{A}(x)2^{−|s|} is dominated by μ_{B}(f(x, s)), then we have μ_{A}(x) = ∑_{s∈S_{x}} μ_{A}(x)2^{−|s|}, which is dominated by ∑_{s∈S_{x}} μ_{B}(f(x, s)), a property we desire.

Following [VL88, BG93, BG95], we formulate the notion of randomized

3.2-4

reductions as follows. For simplicity, we assume that only unbiased random coins are used in randomizations. Let A be a randomized algorithm and x be an input. We are only interested in sequences s of random bits such that A(x) halts using s. Such a random sequence must be finite.

We allow a randomized algorithm (for solving a problem) to produce

3.2-5

incorrect outputs on some sequences of random bits. For example, suppose that a randomized algorithm A computes a reduction from A to B, and suppose that A on input x, with s being the random sequence, produces an output string y. Then the output y is incorrect if x ∈ A but y ∉ B. If A halts on input x with random sequence s and produces a correct output, then (x, s) is called a good input of A.

From now on, we will be interested only in good inputs. Let A be a

3.2-6

randomized algorithm and μ an input distribution of A. A good-input domain of A (with respect to μ) is the set of all pairs (x, s) such that μ(x) > 0, A on input x halts and produces a correct output, and s is the random sequence it generates during the computation. Clearly, A is deterministic on (x, s) and we may view (x, s) as the input of A. If A computes a function f, then we can view f as a deterministic function on (x, s). If A is deterministic on x, then (x, e) is in the good-input domain of A, where e denotes the empty string.

Let Γ be a good-input domain of A. Let Γ(x) = { s: (x, s) ∈ Γ }. We can

3.2-7

see that no string in Γ(x) is a prefix of a different string in Γ(x); otherwise, the longer string cannot be in Γ(x) as the algorithm stops before it can be generated. We say that Γ(x) is non-rare [BG93] if the rarity function of Γ, defined by U_{Γ}(x) = 1/ ∑_{s∈Γ(x)} 2^{−|s|} if μ(x) > 0 and U_{Γ}(x) = 1 otherwise, is

7 polynomial on μ-average.^{1} A good-input domain Γ is called non-rare if for all x, Γ(x) is non-rare.

For all (x, s) ∈ Γ, let

3.2-8

μ_{Γ}(x, s) = μ(x)2^{−|s|}U_{Γ}(x).

Here the factor U_{Γ}(x) is used for normalization (see Definition 2.8 in [BG95] on page 955).

Definition 3 ([BG93, BG95]) Let A be a randomized algorithm with input distribution μ. Then A runs in time polynomial on μ-average if there is a good-input domain Γ of A and an ε > 0 such that Γ is non-rare, and

∑_{(x,s)∈Γ} t^{ε}(x, s)|x|^{−1}μ_{Γ}(x, s) < ∞,

where t(x, s) is the running time of A on input x with random sequence s.

For simplicity, when there is no confusion about the input distribution μ,

3.2-9

we call a randomized algorithm that runs in time polynomial on μ-average a randomized ap-time algorithm.

The probability that a randomized ap-time algorithm A on input x pro-

3.2-10

duces a correct output is 1/U_{Γ}(x), a value that could be small. Blass and Gurevich [BG93, BG95] showed that the algorithm can be iterated to obtain a correct solution with probability 1 in ap-time, provided that the correct output can be verified in ap-time. For the purpose of iteration, we would like to require that the good-input domain of the algorithm be decidable in ap-time with respect to μ_{Γ}. In [BG95], such a good-input domain is called certifiable.

Let (A, μ) be a distributional problem. Let D_{A} be the set of all (posi-

3.2-11

tive and negative) instances of A. When (A, μ) is solvable by a randomized algorithm, we may view a good-input domain of the algorithm as a “randomized” input domain of (A, μ). Sometimes we would like to refer to a good-input domain without specifying a randomized algorithm, and we will call it a randomized input domain of (A, μ).

Let RAP be the class of distributional problems (A, μ) for which there is

3.2-12

a randomized ap-time algorithm A with a good-input domain Γ such that 8 Γ is non-rare, certifiable, and for all (x, s) ∈ Γ, x ∈ A if and only if A(x, s) accepts. RAP is an average-case analogue of ZPP. ^{2} Definition 4 ([BG95]) Let (A, μ_{A}) and (B, μ_{B}) be distributional prob-

1If for all x, U_{Γ}(x) = 1, then the randomized algorithm produces a correct output with probability 1. For our purpose, we only need to require that the value of U_{Γ}(x) be “reasonable” in the sense that U_{Γ} is polynomial on μ-average.

Definition 4-1

lems. Then (A, μ_{A}) is ap-time randomly reducible to (B, μ_{B}), denoted by (A, μ_{A}) ≤_{r}^{ap} (B, μ_{B}), if there is a reduction f such that the following conditions are satisfied.

1. The reduction f is computable by a randomized algorithm in time polynomial on μ_{A}-average with a good-input domain Γ_{A}.

2. Γ_{A} is non-rare and certifiable.

3. For all (x, s) ∈ Γ_{A}, x ∈ A if and only if f(x, s) ∈ B.

4. μ_{Γ_{A}} ⪯_{f}^{ap} μ_{B}.

If the reduction f can be computed by a randomized p-time algorithm,

Definition 4-2

then f is called a randomized p-time reduction.

Clearly, deterministic reductions are a special case of randomized reduc-

3.2-13

tions with good inputs (x, e), where e is the empty string.

The following lemma is straightforward.

3.2-14

Lemma 1 If f : Γ_{A} → B is one-one over Γ_{A}, then μ_{Γ_{A}} ⪯_{f}^{ap} μ_{B} if and only if μ_{Γ_{A}} ⪯^{ap} μ_{B} ∘f.

We will often use the phrase “via (f, Γ_{A})” to emphasize the randomized

3.2-15

reduction f and its non-rare good-input domain Γ_{A}. Lemma 2 (([BG95])) (1) If (A, μ_{A}) ≤_{r}^{ap} (B, μ_{B}) and (B, μ_{B}) is in RAP, then so is (A, μ_{A}). (2) Randomized ap-time reductions are transitive.

2Clearly, for every set A ∈ ZPP and every distribution μ, (A, μ) ∈ RAP. We might as well use AZPP to denote RAP. We may also define ABPP as analogous to BPP, and use ABPP as a notion of easiness.

4 Randomized Isomorphisms

Berman and Hartmanis defined two problems A and B to be p-isomorphic if

4-1

there exists a p-time computable and invertible bijection ϕ : D_{A} → D_{B} such that A ≤_{m}^{p} B via ϕ and B ≤_{m}^{p} A via ϕ^{−1}. For distributional problems (A, μ_{A}) and (B, μ_{B}), Wang and Belanger [WB95] defined that (A, μ_{A}) and (B, μ_{B}) are p-isomorphic if there exists a p-time computable and invertible bijection ϕ : D_{A} → D_{B} such that (A, μ_{A}) ≤_{m}^{p} (B, μ_{B}) via ϕ and (B, μ_{B}) ≤_{m}^{p} (A, μ_{A}) via ϕ^{−1}. Polynomial isomorphisms on distributional problems are transitive.

Let μ and ν be two distributions. Write μ ≈^{p} ν if μ is dominated by ν

4-2

and ν is dominated by μ. Wang and Belanger [WB95] showed the following p-time equivalent of the Cantor-Bernstein-Myhill theorem for distributional problems.

Theorem 1 ([WB95]) Let (A, μ_{A}) ≤_{m}^{p} (B, μ_{B}) via f, and (B, μ_{B}) ≤_{m}^{p} (A, μ_{A}) via g, then (A, μ_{A}) is p-isomorphic to (B, μ_{B}) if both f and g are one-one, length-increasing, p-time computable, and p-time invertible, and μ_{A} ≈^{p} μ_{B} ∘f (here μ_{B} ∘f(x) = μ_{B}(f(x))) and μ_{B} ≈^{p} μ_{A}∘g.

4-3 Note that if f is one-one, then μ ⪯_{f}^{p} ν if and only if μ ⪯ ν ∘f [Gur91]. Using Theorem 1, Wang and Belanger [WB95] showed that all the known distributional NP problems that are complete under p-time many–one reductions are p-isomorphic.

Let π_{1} and π_{2} be functions defined on tuples of strings such that π_{1} returns

4-4

the first element and π_{2} returns the second element.

Next, we consider how to generalize the notion of isomorphisms to the

4-5

setting of randomized reductions. Let (A, μ_{A}) and (B, μ_{B}) be two distributional problems. Recall that the notion of isomorphisms under deterministic reductions is defined to be a bijection between input domains of the underlying problems. Following this framework, we consider bijections Ψ between a randomized input domain of (A, μ_{A}) and a randomized input domain of (B, μ_{B}). Note that a randomized reduction takes a random string as input and does not output one. This leads us to consider π_{1}∘Ψ and π_{1}∘Ψ^{−1} as possible reductions; namely, we would like to transform (encode) each instance of A to a unique instance of B via π_{1}∘Ψ, and transform each instance of B back to a unique instance of A via π_{1}∘Ψ^{−1}. This gives rise naturally to the following definition of isomorphism under randomized reductions.

Definition 5 (A, μ_{A}) is randomly isomorphic to (B, μ_{B}), denoted by (A, μ_{A}) ≡_{r} (B, μ_{B}), if the following conditions hold.

10 1. There exist randomized input domains Γ_{A} of (A, μ_{A}) and Γ_{B} of (B, μ_{B}),

and a bijection Ψ between Γ_{A} and Γ_{B} such that Ψ is ap-time computable on Γ_{A} and Ψ^{−1} is ap-time computable on Γ_{B}.

4-6

2. Let f = π_{1}∘Ψ and g = π_{1}∘Ψ^{−1}. Then (A, μ_{A}) ≤_{r}^{ap} (B, μ_{B}) via (f, Γ_{A}), and (B, μ_{B}) ≤_{r}^{ap} (A, μ_{A}) via (g, Γ_{B}).

Clearly, randomized isomorphisms are transitive.

4-7

Next, we show a randomized ap-time equivalent of the Cantor-Bernstein-

4-8

Myhill theorem for distributional problems as a natural generalization of the p-time equivalent of the Cantor-Bernstein-Myhill theorem.

A (partial) function f : Σ^{∗} × Σ^{∗} → Σ^{∗} (or f : Σ^{∗} × Σ^{∗} → Σ^{∗} × Σ^{∗}) is said

4-9

to be length-increasing if |f(x, y)| > |x| + |y| whenever f(x, y) is defined. Let (A, μ_{A}) and (B, μ_{B}) be two distributional problems. Assume that

4-10

(A, μ_{A}) ≤_{r}^{ap} (B, μ_{B}) via (f, Γ_{A}) and (B, μ_{B}) ≤_{r}^{ap} (A, μ_{A}) via (g, Γ_{B}). In view of Theorem 1, we would first require that f and g be one-one, lengthincreasing, and invertible. We then would like μ_{A} and μ_{B} to have certain relations under f and g. If f and g are deterministic many-one reductions, we have required, as stated in Theorem 1, that μ_{A} ≈^{p} μ_{B}∘f and μ_{B} ≈^{p} μ_{A}∘g. What is needed there is actually the following two requirements: μ_{B}∘f ⪯^{p} μ_{A} and μ_{A}∘g ⪯^{p} μ_{B}; the other parts, namely, μ_{A} ⪯^{p} μ_{B}∘f and μ_{B} ⪯^{p} μ_{A}∘g, are guaranteed by the one-one reductions. In the setting of randomization, these two requirements may be written as follows: (1) for all (x, s) ∈ Γ_{B} and for all s′ ∈ Γ_{A}(g(x, s)): μ_{Γ_{A}}(g(x, s), s′) ⪯^{ap} μ_{B}(x); (2) for all (x, s) ∈ Γ_{A} and for all s′ ∈ Γ_{B}(f(x, s)): μ_{Γ_{B}}(f(x, s), s′) ⪯^{ap} μ_{A}(x). We can obtain, as definitions, equivalents of these two statements without using s and s′. Since these two statements are symmetric, we present the equivalent of the first statement below. (The equivalent of the second statement can be obtained similarly.)

Assume that (A, μ_{A}) ≤_{r}^{ap} (B, μ_{B}) via (f, Γ_{A}). For all x ∈ D_{A}, let l_{A}(x) =

4-11

min { |s| : s ∈ Γ_{A}(x) }. Then μ_{Γ_{A}} on g is weakly dominated by μ_{B} if for all x ∈ range(g), μ_{A}(x)2^{−l_{A}(x)} ⪯^{ap} μ_{B}(π_{1}(g^{−1}(x))).

To prove Theorem 2, we would also like to acquire the following property.

4-12

Definition 6 Let Γ be a randomized input domain of (A, μ_{A}). Then Γ is selectable if there is a p-time computable function ξ : D_{A} → Σ^{∗} such that for every x ∈ D_{A}, (x, ξ(x)) ∈ Γ. The function ξ is called a selection function of Γ.

11 Theorem 2 Suppose (A, μ_{A}) ≤_{r}^{ap} (B, μ_{B}) via (f, Γ_{A}) and (B, μ_{B}) ≤_{r}^{ap} (A, μ_{A}) via (g, Γ_{B}). Then (A, μ_{A}) ≡_{r} (B, μ_{B}) if the following conditions hold.

1. Both Γ_{A} and Γ_{B} are certifiable and selectable.

2. Both f : Γ_{A} → B and g : Γ_{B} → A are one-one, length-increasing, and ap-time invertible.

3. The distribution μ_{Γ_{A}} on g is weakly dominated by μ_{B}, and μ_{Γ_{B}} on f is weakly dominated by μ_{A}.

Proof of Theorem 2 By assumption of the reductions, for all (x, s) ∈ Γ_{A},

Proof of Theorem 2-1

f(x, s) is defined; and, for all (x, s) ∈ Γ_{B}, g(x, s) is defined. Without loss of generality, assume that, for (x, s) ∉ Γ_{A}, f(x, s) is not defined, and for (x, s) ∉ Γ_{B}, g(x, s) is not defined. Hence, f is a deterministic function on input domain Γ_{A}, and g is a deterministic function on input domain Γ_{B}.

By assumption, both Γ_{A} and Γ_{B} are selectable. Let ξ_{A} and ξ_{B} be the

Proof of Theorem 2-2

p-time computable selection functions of Γ_{A} and Γ_{B}, respectively. Define functions F : Γ_{A} → Γ_{B} and G : Γ_{B} → Γ_{A} as follows.

Proof of Theorem 2-3

∀(x, s) ∈ Γ_{A} : F (x, s) = (f(x, s), ξ_{B}(f(x, s)))  (1)
∀(x, s) ∈ Γ_{B} : G(x, s) = (g(x, s), ξ_{A}(g(x, s)))  (2)

Since both f and g are one-one and length-increasing, both F and G are

Proof of Theorem 2-4

one-one and ap-time computable.

We have

Proof of Theorem 2-5

F^{−1}(x, ξ_{B}(x)) = (π_{1}(f^{−1}(x)), π_{2}(f^{−1}(x)))
G^{−1}(x, ξ_{A}(x)) = (π_{1}(g^{−1}(x)), π_{2}(g^{−1}(x))).

It is easy to see that both F^{−1} and G^{−1} are ap-time computable. They

Proof of Theorem 2-6

are also length-decreasing; namely, |F^{−1}(x, s)| < |x| + |s| and |G^{−1}(x, s)| < |x| + |s|. Hence, the sets R_{1}, R_{2}, S_{1}, and S_{2} defined below are all ap-time decidable.

R_{1} = { (G∘F)^{k}(x, s) : k ≥ 0, (x, s) ∉ G(Γ_{B}), and (x, s) ∈ Γ_{A} if k = 0 } ,
R_{2} = { G∘(F ∘G)^{k}(x, s) : k ≥ 0, and (x, s) ∉ F (Γ_{A}) } ,
S_{1} = { (F ∘G)^{k}(x, s) : k ≥ 0, (x, s) ∉ F (Γ_{A}), and (x, s) ∈ Γ_{B} if k = 0 } ,
S_{2} = { F ∘(G∘F)^{k}(x, s) : k ≥ 0, and (x, s) ∉ G(Γ_{B}) } .

12 Following the proof given in [BH77], we can show that Γ_{A} = R_{1} ∪ R_{2},

Proof of Theorem 2-7

R_{1} ∩ R_{2} = ∅, and Γ_{B} = S_{1} ∪ S_{2}, S_{1} ∩ S_{2} = ∅. Also, for every (x, s) ∈ Γ_{A}, (x, s) ∈ R_{1} if and only if F (x, s) ∈ S_{2}, and (x, s) ∈ R_{2} if and only if F (x, s) ∈ S_{1}. Similarly, for every (x, s) ∈ Γ_{B}, (x, s) ∈ S_{1} if and only if G(x, s) ∈ R_{2}, and (x, s) ∈ S_{2} if and only if G(x, s) ∈ R_{1}.

Let, for all (x, s) ∈ Γ_{A},

Proof of Theorem 2-8

Ψ(x, s) = \{ \begin{matrix}F (x, s), & if (x, s) ∈ R_{1}, \\ G^{−1}(x, s), & if (x, s) ∈ R_{2}. \end{matrix}

Then the inverse of Ψ is given by, for all (x, s) ∈ Γ_{B},

Ψ^{−1}(x, s) = \{ \begin{matrix}G(x, s), & if (x, s) ∈ S_{1}, \\ F^{−1}(x, s), & if (x, s) ∈ S_{2}. \end{matrix}

The function Ψ is the desired bijection between Γ_{A} and Γ_{B}.

Next, we show that (A, μ_{A}) ≤_{r}^{ap} (B, μ_{B}) via (π_{1}∘Ψ, Γ_{A}). (We can similarly

Proof of Theorem 2-9

show that (B, μ_{B}) ≤_{r}^{ap} (A, μ_{A}) via (π_{1}∘Ψ^{−1}, Γ_{B}).)

Let (x, s) ∈ Γ_{A}.

Proof of Theorem 2-10

Case 1: (x, s) ∈ R_{1}. Then π_{1} ∘Ψ(x, s) = f(x, s). Since by assumption,

Proof of Theorem 2-11

(A, μ_{A}) ≤_{r}^{ap} (B, μ_{B}) via (f, Γ_{A}), we have x ∈ A if and only if f(x, s) ∈ B and μ_{Γ_{A}} ⪯_{f}^{ap} μ_{B}. Since f is one-one over Γ_{A}, it follows from Lemma 1 that μ_{Γ_{A}} ⪯^{ap} μ_{B} ∘f. By the definition of F, we have π_{1}∘Ψ(x, s) = f(x, s). Thus, we have x ∈ A if and only if π_{1}∘Ψ(x, s) ∈ B, and μ_{Γ_{A}} ⪯^{ap} μ_{B}∘(π_{1}∘Ψ). Since π_{1}∘Ψ is one-one, we have that μ_{Γ_{A}} is weakly dominated by μ_{B} with respect to π_{1}∘Ψ.

Case 2: (x, s) ∈ R_{2}. Then g^{−1}(x) is defined and it follows from Equation

Proof of Theorem 2-12

(2) that π_{1} ∘Ψ(x, s) = π_{1} ∘G^{−1}(x, s) = π_{1}(g^{−1}(x)). Since g^{−1}(x) is defined, (π_{1}∘g^{−1}(x), π_{2}∘g^{−1}(x)) ∈ Γ_{B}. So we have π_{1}∘g^{−1}(x) ∈ B if and only if g(π_{1}∘ g^{−1}(x), π_{2}∘g^{−1}(x)) ∈ A. Since g(π_{1}∘g^{−1}(x), π_{2}∘g^{−1}(x)) = x, this implies that x ∈ A if and only if π_{1}∘Ψ(x, s) ∈ B. By Condition 3 in the statement of the theorem, μ_{A}(x)2^{−l_{A}} ⪯^{ap} μ_{B}(π_{1}(g^{−1}(x))), where l_{A} = min { |s| : s ∈ Γ_{A}(x) }. Since |s| ≥ l_{A}, we have μ_{Γ_{A}}(x, s) = μ_{A}(x)2^{−|s|} ≤ μ_{A}(x)2^{−l_{A}}, which implies that μ_{Γ_{A}} is weakly dominated by μ_{B}∘(π_{1}∘Ψ). Again, since π_{1}∘Ψ is one-one, we have that μ_{Γ_{A}} is weakly dominated by μ_{B} with respect to π_{1} ∘Ψ. This completes the proof.

Proof of Theorem 2 □

13 Built on rich structures of complete sets, Berman and Hartmanis [BH77]

4-13

obtained a sufficient condition under which reductions are guaranteed to be p-time invertible. In particular, let A be a set for which two p-time computable functions S_{A}(·, ·) and D_{A}(·) exist with the following properties:

(1) (∀x, y)[S_{A}(x, y) ∈ A if and only if x ∈ A], and (2) (∀x, y)[D_{A}(S_{A}(x, y)) = y]. Then if f is any p-time reduction of some set C to A, the map f′(x) = S_{A}(f(x), x) is one-one and invertible in p-time and reduces C to A. An easy proof shows that all the known, standard NP-complete sets do satisfy these two properties [BH77]. It follows from the p-time equivalent of the Cantor-Bernstein-Myhill theorem for (worst-case) decision problems that all the known standard NP-complete problems are p-isomorphic.

For distributional problems, however, the reductions need to be easily

4-14

invertible and preserve the probability distributions. Unfortunately, no functions such as S_{A} and D_{A} above are known that preserve the probabilities in a useful way. For w ∈ A, we would need the probability of D_{A}(w) to depend on the probability function associated to the arbitrary set C, and hence to an undetermined probability function. So to use Theorem 2, we will investigate individual reduction used in each completeness proof. Fortunately, this task can often be accomplished by using the existing completeness proofs, with some minor modifications if necessary. Using Theorem 2, we can show that all the known average-case NP-complete problems are indeed randomly isomorphic.

5 Isomorphism Proofs

Levin [Lev86] (see also [Gur91]) showed that any p-time computable distri-

5-1

bution on string x is dominated by a uniform distribution on strings whose length is polynomially related to |x|. Based on that, Wang and Belanger proved the following Distribution Controlling Lemma [WB95].

Lemma 3 (Distribution Controlling Lemma) Let μ be a p-time computable distribution. If there exists a polynomial p such that for all x, μ(x) > 2^{−p(|x|)}, then there is a total, one-one, p-time computable and p-time invertible function α: Σ^{∗} → Σ^{∗} such that for all x, 4 · 2^{−|α(x)|} ≤ μ(x) < 20 · 2^{−|α(x)|}.

We first use distributional halting problems as an example of obtaining

5-2

an isomorphism proof.

14

5.1 Distributional Halting

Let M_{1}, M_{2}, … be a fixed enumeration of nondeterministic Turing machines

5.1-1

in which the index i is a binary integer that codes up the symbols, states, and transition table of the i-th Turing machine M_{i}.

Distributional Halting (Version 1)

5.1-2

Instance. Binary strings i, x, and a unary notation 1^{n} representing positive integer n, where i is a positive integer in binary form.

Question. Does M_{i} accept x within n steps?

5.1-3

Distribution. Uniform; namely, the distribution on instance (i, x, 1^{n}) is

5.1-4

proportional to 2^{−(l+m)}l^{−2}m^{−2}n^{−2}, where l = |i| and m = |x|.

Distributional Halting (Version 2)

5.1-5

Instance. Binary strings i, x, and t, where i is a positive integer. Question. Does M_{i} accept x within |t| steps?

5.1-6

Distribution. Uniform; namely, the distribution on instance (i, x, t) is

5.1-7

proportional to 2^{−(l+m+n)}l^{−2}m^{−2}n^{−2}, where l = |i|, m = |x|, and n = |t|.

Let (K, μ_{K}) and (K′, μ_{K′}) denote the halting problem version 1 and ver-

5.1-8

sion 2, respectively. (K, μ_{K}) is is complete for DistNP under p-time many– one reductions [Gur91, BDCGL92, WB95]. (K′, μ_{K′}) (note that μ_{K′} is flat) is complete for DistNP under randomized p-time reductions [Gur91, Wan97].

Theorem 3 (K, μ_{K}) ≡_{r} (K′, μ_{K′}).

Proof of Theorem 3 Let Γ_{K} = { (y, s): y = (i, x, 1^{n}) and |s| = n }. Then

Proof of Theorem 3-1

Γ_{K} is certifiable, non-rare (the rarity function U_{Γ}(x) = 1), and selectable. For a given string y = (i, x, 1^{n}), let h be a function that pads the program i such that h is p-time computable, p-time invertible, |h(i)| > |i| + O(1), and M_{h(i)} = M_{i}. Let h(i) = j; then |h^{−1}(j)| = |j| − O(1). For all (y, s) ∈ Γ_{K}, let f(y, s) = (h(π_{1}(y)), π_{2}(y), s). Then f is one-one, length-increasing, p-time computable, and p-time invertible. Hence, for all (y, s) ∈ Γ_{K}, we have y ∈ K if and only if (π_{1}(y), π_{2}(y), s) ∈ K′ if and only if (h(π_{1}(y)), π_{2}(y), s) ∈ K′. This implies that y ∈ K if and only if f(y, s) ∈ K′. By definition, μ_{Γ_{K}}(y, s) = μ_{K}(y)2^{−|s|}, which is proportional to μ_{K′}(f(y, s)). Hence, μ_{Γ_{K}}(y, s) is dominated by μ_{K′}(f(y, s)). Thus, (K, μ_{K}) ≤_{r}^{ap} (K′, μ_{K′}) via (f, Γ_{K}).

Next, we show that (K′, μ_{K′}) is polynomially reducible to (K, μ_{K}) via

Proof of Theorem 3-2

a length-increasing, one-one, deterministic reduction. We can see that 15 (K′, μ_{K′}) ≤_{m}^{p} (K, μ_{K}) by a reduction that maps (i, x, s) to (h(i), x, 1^{|s|}). But this reduction is not one-one and so cannot be used. We will construct a different reduction using a standard technique as shown in [WB95]. Note that μ_{K′} satisfies the hypothesis of the Distribution Controlling Lemma. So there is a total, one-one, p-time computable, and p-time invertible function α such that for all y ∈ D_{K′}, 4 · 2^{−|α(y)|} < μ_{K′}(y) < 20 · 2^{−|α(y)|}. Let M be a nondeterministic Turing machine M that accepts K′ in polynomial time. Define a Turing machine M′ as follows: On binary input w, if α^{−1}(w) is defined, then M′ simulates M on α^{−1}(w) and rejects otherwise. So for all y ∈ D_{K′}, M accepts y if and only if M′ accepts α(y). It is easy to see that M′ on input α(y) is bounded in polynomial time, and we call it p(|y|).

Let i be a program such that M′ = M_{i}. Let g(y) = (i, α(y), 1^{p(|y|)}). Then

Proof of Theorem 3-3

g is one-one, length-increasing, p-time computable, and p-time invertible. By construction, y ∈ K′ if and only if g(y) ∈ K. Moreover, μ_{K} ∘g(y) ≈^{p} 2^{−|α(y)|} ≈^{p} μ_{K′}(y). Thus, we have (K′, μ_{K′}) ≤_{m}^{p} (K, μ_{K}) via g.

Conditions 1 and 2 of Theorem 2 regarding Γ_{K′} are obviously satisfied.

Proof of Theorem 3-4

To complete this direction, we need only show that Condition 3 of Theorem 2 holds. For this purpose, we view function g as a function defined on Γ_{K′} = { (y, e): y ∈ D_{K′} } by g(y, e) = g(y). Let z ∈ range(g). Then z = g(y) for some y ∈ D_{K′}. Hence, we have μ_{K}(z) ≈^{p} μ_{K′} ∘(g^{−1}(z)). Let l_{K} = min { |s| : s ∈ Γ_{K}(z) }. Then μ_{K}(z)2^{−l_{K}} < μ_{K}(z). This implies that μ_{K}(z)2^{−l_{K}} is dominated by μ_{K′}(π_{1}(g^{−1}(z))). The first statement of Condition 3 of Theorem 2 is therefore satisfied. We now show that the second statement of Condition 3 is also satisfied. Let y = (i, x, s) ∈ range(f). Then f^{−1}(y) = (y′, s), where y′ = (h^{−1}(i), x, 1^{|s|}). Hence, π_{1}(f^{−1}(y)) = (h^{−1}(i), x, 1^{|s|}). Since |h^{−1}(i)| = |i| − O(1), this implies that μ_{Γ_{K′}}(y) is dominated by μ_{K}(π_{1}(f^{−1}(y))).

We have therefore verified that all the conditions of Theorem 2 are satis-

Proof of Theorem 3-5

fied, and so (K, μ_{K}) ≡_{r} (K′, μ_{K′}).

Proof of Theorem 3 □

5.2 Distributional Tiling and Graph Spot Coloring

A tile is a square with a symbol on each corner. Tiles may not be rotated or

5.2-1

turned over. We assume that there are infinitely many copies of each type of tile. By a tiling of an n × n square we mean an arrangement of n^{2} tiles to cover the entire square so that the symbols on the touching corners of

16 adjacent tiles are the same.

Distributional Tiling

5.2-2

Instance. A finite set of tiles T, a unary notation 1^{n} for a positive integer n, and a sequence S = s_{1}s_{2} … s_{k} (k ≤ n) of tiles that match each other; that is, the symbols on the touching corners of s_{i} and s_{i+1} are the same.

Question. Can S be extended to tile an n × n square using tiles from T?

5.2-3

Distribution. Uniform; namely, the distribution is proportional to

5.2-4

Pr[T]n^{−2}Pr[S], where Pr[T] is the probability of choosing T,^{3} and Pr[S] is the probability of choosing S. S is chosen by first choosing k at random with probability 1/n, then choosing the first tile s_{1} at random from T, and choosing the s_{i} (i > 1) sequentially and uniformly at random from those tiles in T that match s_{i−1}.

Levin [Lev86] showed that the distributional tiling problem is average-case

5.2-5

NP-complete under a deterministic reduction. Gurevich [Gur91] provided a detailed proof for tiles with marked edges, where each edge of a tile is marked with a symbol; in the tiling of a square, symbols on the touching edge of adjacent tiles are the same. Belanger and Wang [BW93, WB95] presented a simpler proof. Distributional tiling with marked corners and with marked edges are polynomially isomorphic.

We are interested in the following variant of distributional tiling on tiles

5.2-6

with marked corners. First, the set of tiles T is fixed; so T is no longer a component of an instance. Second, in the S component of an instance, the two corners at the same side of a tile have the same binary digit. The first tile in S has a special symbol on its lower-left corner. It is easy to see that there exists T, denote it by T , such that this variant of distributional tiling is p-isomorphic to the standard distributional tiling. (For example, we can construct T based on a fixed Turing machine that accepts K.) Denote by (T , μ_{T}) this average-case NP-complete variant.

Venkatesan and Levin [VL88] studied the following edge-coloring problem

5.2-7

for directed graphs (digraphs, in short), where nodes are labeled and may have self-loops. For convenience, we assume that self-loops with single direction and self-loops with double directions are distinct. (This assumption can be used to simplify proofs.) Let G be such a digraph. An edge of G may be colored or left blank (i.e., uncolored), with a constant number of colors. A spot in a colored digraph is a 3-node subgraph with induced colored edges

17 (including self-loops if there are any) and the nodes unlabeled. It is easy to see that there are only a constant number of different spots. The coloration C(G) of G consists of the set of all spots induced from the colored graph G and the number of blank edges.

3One can use one’s favorite distribution to select T or simply select it uniformly at random among binary strings, since T is coded in binary.

Write f(n) ∼ g(n) if lim_{n→∞} f(n)/g(n) = 1.

5.2-8

Distributional Graph Spot Coloring

5.2-9

Instance. A digraph G of n nodes, a set C of spots, and a unary notation 1^{k} for a positive integer k, where k < \binom{n}{2}.

Question. Can G be colored such that C(G) = (C′, k) and C′ ⊆ C? (If

5.2-10

so, we then say that G is colorable.)

Distribution. Uniform: First choose a positive integer n with probability

5.2-11

Θ(n^{−2}), then randomly and independently choose a directed graph of n nodes with uniform probability 4^{−\binom{n}{2}}3^{−n} ∼ 2^{−n^{2}}, a set of spots with probability Θ(1), the number of blank edges k with probability Θ(n^{−2}). Hence, the probability distribution is proportional to n^{−4}2^{−n^{2}}, which is flat.

Let (E, μ_{E}) denote the distributional graph spot-coloring problem.

5.2-12

Venkatesan and Levin [VL88] (a slightly different proof was given in [Ven91]) showed that (E, μ_{E}) is average-case NP-complete under a randomized reduction.^{4}

Theorem 4 (T , μ_{T}) ≡_{r} (E, μ_{E}).

Proof of Theorem 4 For a large part, we follow a proof given in [VL88],

Proof of Theorem 4-1

showing that distributional graph spot-coloring is average-case NP-complete. To arrive quickly to the point showing why a randomized isomorphism exists, we will omit proofs to certain lemmas; all of the missing proofs can be found in [VL88, Ven91].

A tournament is an acyclic (except for self-loops) complete digraph. Any

Proof of Theorem 4-2

tournament contains a Hamiltonian path; there is a deterministic p-time algorithm that starts from the node with smallest label and finds a Hamiltonian path uniquely (see, e.g., [Liu68]). Let k = |T |. Let t_{1}, t_{2}, …, t_{k} be a Hamiltonian path of a tournament T found in this way. Define the code for a node u to be the binary string of length 2|T | of the form

18 c(t_{1}, u)c(u, t_{1}) … c(t_{k}, u)c(u, t_{k}), where c(u, v) = 1 if u → v and 0 otherwise [BES80]. So T determines the code for u uniquely.

4What would be the minimum number of colors that can make the distributional graph spot coloring problem complete for DistNP? That is an interesting question. It was claimed that 20 colors [VL88], or even much fewer colors [Ven91], are sufficient.

We now construct a randomized reduction f from (T , μ_{T}) to (E, μ_{E}). Let

Proof of Theorem 4-3

X = (1^{n}, S) (|S| < n) be an instance of (T , μ_{T}).

The reduction f first partitions {1, …, 2n^{2}+k−1} at random into disjoint

Proof of Theorem 4-4

sets T, L, U, with |T | = k = ⌈2 log n⌉+1, |L| = n^{2}, and then randomly adds edges to generate a random graph of 2n^{2}+k−1 nodes. Let r(n) be the number of random bits required in this random process. (In [VL88], it indicates that r(n) = 5n^{4} is sufficient.) Since there are 2^{(2n^{2}+k−1)^{2}} many graphs and we need extra random bits to generate a partition, r(n) > (2n^{2} + k − 1)^{2}. Clearly, a partition and a graph can be uniquely constructed in time polynomial of n when r(n) random bits are given.

Among the random graphs so generated, we are particularly interested in

Proof of Theorem 4-5

the ones that satisfy the following conditions.

1. T is a tournament.

2. T is the set of all nodes with double-direction self-loops and L is the set of all nodes with single-direction self-loops. (Self-loops are used to enforce the graph structure and the color pattern.)

3. Every node in L ∪ U is connected to every node in T.

4. All unlooped nodes (i.e., nodes in U) have distinct codes with respect to T.

5. Let v_{1}, v_{2}, …, v_{|U|} be the nodes in U in the decreasing order of codes with respect to T. If the symbol of the right side of the i-th tile of S is 0, then v_{i} → v_{i+1} is the only edge between v_{i} and v_{i+1}; if the symbol is 1, then v_{i} ← v_{i+1} is the only edge. If i ≥ |S|, then there are no edges between v_{i} and v_{i+1}.

Note that the last condition above gives an encoding of S in the graph.

Proof of Theorem 4-6

Also, in [VL88], it was required that T be the unique k-node tournament. In our construction, all nodes in T are with double-direction self-loops, and no other nodes have such self-loops. This makes T unique. Let G denote the resultant graph; we call it a tiling graph. Venkatesan and Levin [VL88] showed that there are sufficiently many tiling graphs.

Lemma 4 ([VL88]) The probability that G is a tiling graph is at least Ω(n^{−d}) for some constant d > 1.

19 Let Γ_{T} (X) = { s : |s| = r(n) and s produces a tiling graph G from X }.

Proof of Theorem 4-7

Then Γ_{T} = { (X, s) : s ∈ Γ_{T} (X) } is a good-input domain of f. It follows from Lemma 4 that U_{Γ_{T}} (X) = Ω(n^{−d}) and so Γ_{T} is non-rare. Also, given a random sequence s, it is easy (in p-time) to check whether the graph generated by s is a tiling graph.

Based on the structures of G, Venkatesan and Levin [VL88] (see also

Proof of Theorem 4-8

[Ven91]) constructed a color specification (C, b) in time polynomial of n, where C is a finite set of spots and b = O(\sqrt{n}) such that the following lemma holds true.

Lemma 5 ([VL88]) For every random string s ∈ Γ_{T} (X), X is a positive instance of distributional tiling T if and only if the graph G produced by f(X, s) is colorable under the color specification (C, b). Moreover, the tiling can be constructed in polynomial time from a coloring.

The desired reduction f(X, s), for (X, s) ∈ Γ_{T}, is the digraph G as de-

Proof of Theorem 4-9

scribed above, plus the color specification (C, b).

It is easy to see that f is one-one, length-increasing, and p-time com-

Proof of Theorem 4-10

putable on input (X, s) ∈ Γ_{T}. To see that μ_{Γ_{T}} (X, s) is dominated by μ_{E}(f(X, s)), we note that μ_{E}(f(X, s)) is proportional to (2n^{2} + k − 1)^{−4}2^{−(2n^{2}+k−1)^{2}}, and μ_{Γ_{T}} (X, s) = Pr[X]2^{−|s|} ≤ 2^{−|s|} = 2^{−r(n)}, where Pr[X] is the probability distribution of X. Since −r(n) < −(2n^{2} + k − 1)^{2}, μ_{Γ_{T}} (X, s) is dominated by μ_{E}(f(X, s)).

We now show that f is p-time invertible. Given a tiling graph G, we can

Proof of Theorem 4-11

easily identify T, L, and U by checking whether a node has a double-direction self-loop, a single-direction self-loop, or no self-loop. Our task is therefore to find S that is embedded in G. From T, we can obtain distinct codes for nodes in U and so S can be identified. The partition T, L, and U, and the edges of G reveal the random string s that generates the graph. Clearly, this algorithm can be carried out in time polynomial of n. This algorithm also shows that Γ_{T} is selectable.

Next, we consider the other direction. Since μ_{E} satisfies the hypothesis

Proof of Theorem 4-12

of the Distribution Controlling Lemma, it has been shown in [WB95] that (E, μ_{E}) ≤_{m}^{p} (T , μ_{T}) via a deterministic reduction g that is one-one, p-time computable, and p-time invertible. Moreover, μ_{E} ≈^{p} μ_{T} ∘g. So for every X ∈ range(g), where X = (1^{n}, S) ∈ D_{T}, and for every s ∈ Γ_{T} (X), μ_{Γ_{T}} (X, s) < μ_{T} (X), which is dominated by μ_{E}(g^{−1}(X)). This shows that the first part of Condition 3 of Theorem 2 is satisfied.

20 We verify that the second part of Condition 3 of Theorem 2 is also satis-

Proof of Theorem 4-13

fied. First, we may view g as a function defined on Γ_{E} = { (Y, e) : Y ∈ D_{E} } by g(Y, e) = g(Y). Let Y ∈ range(f), then Y = (G, (C, b)) = f((1^{n}, S), s) for a unique ((1^{n}, S), s) ∈ Γ_{T}, where |S| < n, and |G| = 2n^{2} + k − 1, where |G| denotes the number of nodes in G. Hence, μ_{Γ_{E}}(Y, e) = μ_{E}(Y) ≈^{p} |G|^{−4}2^{−|G|^{2}}. Since μ_{T} (1^{n}, S) is proportional to n^{−2}c^{−|S|} for some constant c (c ≤ |T |) and |S| < n, we have that μ_{Γ_{E}}(Y, e) is dominated by μ_{T} (1^{n}, S) = μ_{T} (π_{1}(f^{−1}(Y))).

From Theorem 2, this completes the proof.

Proof of Theorem 4-14

Proof of Theorem 4 □

5.3 Distributional Matrix Transformation

A square matrix X is called unimodular if all entries in X are integers and

5.3-1

its determinant det(X) = 1. Let SL_{2}(ZZ) denote the set of 2 × 2 unimodular matrices. Define the size of a unimodular matrix X, denoted by |X|, to be the length of the binary representation of the maximal absolute value of its entries.

The distributional matrix transformation problem deals with linear trans-

5.3-2

formations on 2×2 unimodular matrices. A linear transformation of SL_{2}(ZZ) is a function T : SL_{2}(ZZ) → SL_{2}(ZZ) such that T (∑ X_{i}) = ∑ T (X_{i}) whenever all the X_{i} and ∑ X_{i} are unimodular matrices. (Note that in general, SL_{2}(ZZ) is not closed under addition.) A linear transformation of SL_{2}(ZZ) can be represented by a 4 × 4 integer matrix, and it is decidable in polynomial time whether a given 4 × 4 integer matrix represents a linear transformation of SL_{2}(ZZ) [Gur91, BG95].

Let T be a linear transformation and let M(T) be its 4×4 integer matrix

5.3-3

representation. Define the size of T to be the length of the largest absolute value (in the binary notation) of entries in M(T). Gurevich [Gur91] (see also [BG95]) showed that the uniform distribution of T among all linear transformations of size l is Θ(l^{−1}2^{−2l}).

Distributional Matrix Transformation

5.3-4

Instance. A unimodular matrix X, a finite set S of linear transformations of unimodular matrices, and a unary notation 1^{n} for a positive integer n.

Question. Does a linear transformation T exist, where T = T_{1}∘T_{2}∘…∘T_{k},

5.3-5

k ≤ n, T_{i} ∈ S, such that T (X) is the identity matrix?

Distribution. The three components are chosen randomly and indepen-

5.3-6

dently. The integer component n is chosen with respect to the default uniform

Wang Randomized Reductions (Ref)

21 distribution 1/n^{2}. The unimodular component X is chosen with probability |X|^{−2}2^{−2|X|}. Linear transformations are chosen with respect to the uniform distribution on transformations of the same size. Finally, the probability of S is proportional to the product of the probabilities of the members in S.

Let (T, μ_{T}) denote the distributional matrix transformation problem.

5.3-7

Blass and Gurevich [BG95] showed that (T, μ_{T}) is average-case NP-complete under a randomized reduction. Based on that we can show the following result, and we leave the proof to the reader.

Theorem 5 (K, μ_{K}) ≡_{r} (T, μ_{T}).

We can also show that the distributional matrix representability problem

5.3-8

with flat distribution [VR92] is randomly isomorphic to (K, μ_{K}). The reader is referred to [VR92] for a definition of the problem, and we again leave the isomorphism proof to the reader.

Acknowledgments

I am grateful to Jay Belanger for several interesting discussions and for proofreading an early draft of this paper. I thank the two anonymous referees for several useful suggestions.

Acknowledgment of support: Supported in part by NSF under grant CCR-9424164 and by a research grant from the University of North Carolina at Greensboro.

References

[BDCGL92] 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.

[BES80] L. Babai, P. Erdos, and M. Selkow. Random graph isomorphism. SIAM Journal on Computing, 9:628–635, 1980.

22 [BG93] A. Blass and Y. Gurevich. Randomizing reductions of search

problems. SIAM Journal on Computing, 22:949–975, 1993.

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

[BH77] L. Berman and J. Hartmanis. On isomorphisms and density of NP and other complete sets. SIAM Journal on Computing, 2:305–322, 1977.

[BW93] J. Belanger and J. Wang. Isomorphisms of NP-complete problems on random instances. In Proceedings of the 8th Annual Conference on Structure in Complexity Theory, pages 65–74, Los Alamitos, CA, 1993. IEEE Computer Society Press.

[BW97] J. Belanger and J. Wang. No NP problems over ranking of distributions are harder. Theoretical Computer Science, 181:229–245, 1997.

[GS87] Y. Gurevich and S. Shelah. Expected computation time for hamiltonian path problem. SIAM Journal on Computing, 16:486–502, 1987.

[Gur87] Y. Gurevich. Complete and incomplete randomized NP problems. In Proceedings of the 28th Annual Symposium on Foundations of Computer Science, pages 111–117, Los Alamitos, CA, 1987. IEEE Computer Society Press.

[Gur91] Y. Gurevich. Average case completeness. Journal of Computer and System Sciences, 42:346–398, 1991.

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

[Joh84] D. Johnson. The NP-completeness column: an ongoing guide. Journal of Algorithms, 5:284–299, 1984.

23 [Ko83] K. Ko. On the definition of some complexity classes of real

numbers. Mathematical Systems Theory, 16:95–109, 1983.

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

[Liu68] C. L. Liu. Introduction to Combinatorial Mathematics. McGraw-Hill, New York, 1968.

[Ven91] R. Venkatesan. Average-Case Intractability. PhD thesis, Boston University, 1991.

[VL88] R. Venkatesan and L. Levin. Random instances of a graph coloring problem are hard. In Proceedings of the 20th Annual Symposium on Theory of Computing, pages 217–222, New York, 1988. ACM Press.

[VR92] R. Venkatesan and S. Rajagopalan. Average case intractability of diophantine and matrix problems. In Proceedings of the 24th Annual Symposium on Theory of Computing, pages 632–642, New York, 1992. ACM Press.

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

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

[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.

24