BRICS RS-94-2 A. E. Andreev: Complexity of Nondeterministic Functions

BRICS

Basic Research in Computer Science

Complexity of Nondeterministic Functions

Alexander E. Andreev

BRICS Report Series RS-94-2 ISSN 0909-0878 February 1994 Copyright \begin{matrix}c \\ ◯ \end{matrix} 1994, BRICS, Department of Computer Science

University of Aarhus. All rights reserved.

Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy.

See back inner page for a list of recent publications in the BRICS Report Series. Copies may be obtained by contacting:

BRICS Department of Computer Science University of Aarhus Ny Munkegade, building 540 DK - 8000 Aarhus C Denmark

Telephone: +45 8942 3360
Telefax: +45 8942 3255
Internet: BRICS@daimi.aau.dk

Complexity of Nondeterministic Functions

Alexander E. Andreev^{∗}

Department of Mechanics and Mathematics Moscow State University, Moscow, 119899, Russia

E-mail: andreev@matis.math.msu.su

Abstract

The complexity of a nondeterministic function is the minimum possible complexity of its determinisation. The entropy of a nondeterministic function, F, is minus the logarithm of the ratio between the number of determinisations of F and the number of all deterministic functions.

We obtain an upper bound on the complexity of a nondeterministic function with restricted entropy for the worst case.

These bounds have strong applications in the problem of algorithm derandomization. A lot of randomized algorithms can be converted to deterministic ones if we have an effective hitting set with certain parameters (a set is hitting for a set system if it has a nonempty intersection with any set from the system).

Linial, Luby, Saks and Zuckerman (1993) constructed the best effective hitting set for the system of k-value, n-dimensional rectangles. The set size is polynomial in k(log n)/ϵ.

Our bounds of nondeterministic functions complexity offer a possibility to construct an effective hitting set for this system with almost linear size in k(log n)/ϵ.

∗Research finished while visiting the Computer Science Department of Aarhus University.

The visit was funded by BRICS, Centre of the Danish National Research Foundation.

The research was supported by the ESPRIT II BRA Programme of the EC under contract #7141 (ALCOM II), by Grant N 93-011-16005 of the Russian Fund for Fundamental Researches, and by Grant N 93-1-60-15 of the Russian Ministry of Science and Education.

Contents

1 Introduction 3 1.1 Computation and complexity of nondeterministic functions 3 1.2 Previous and new results . . . . . . . . . . . . . . . . . . . 5 1.3 Derandomization problem and nondeterministic functions

complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

2 Complexity bounds for the worst case 9 2.1 Lower and preliminary upper bounds . . . . . . . . . . . . 9 2.2 Nonconstructive upper bound for hitting set size . . . . . 11 2.3 Main decomposition methods . . . . . . . . . . . . . . . . 14 2.4 Complexity of the functions with uniform entropy …. 17 2.5 Uniform mapping classes . . . . . . . . . . . . . . . . . . . 19 2.6 Complexity of the functions with big entropy . . . . . . . 23 2.7 General case . . . . . . . . . . . . . . . . . . . . . . . . . . 30

3 Hitting set construction 34 3.1 The case of not too small entropy . . . . . . . . . . . . . . 34 3.2 Hash classes of functions . . . . . . . . . . . . . . . . . . 36 3.3 The case of small entropy . . . . . . . . . . . . . . . . . . 39

Acknowledgments 42

References 42

Figures 45

1 Introduction

1.1 Computation and complexity of nondeterministic functions

Let A and B be finite sets. By Hom(A, B) we denote the system of all functions (mappings) from the set A into the set B. By B^{∗} we denote the system of all nonempty subsets of the set B. We suppose, that there is no difference between element b of the set B and element {b} of the set B^{∗}. In that way B ⊆ B^{∗}. We define

HOM(A, B) = Hom(A, B^{∗}) .

We say that functions from the set HOM(A, B) are nondeterministic functions from A into B. It is easy to see, that

Hom(A, B) ⊆ HOM(A, B) .

Now we define some relations between the functions from HOM(A, B). For

f ∈ Hom(A, B) , F ∈ HOM(A, B) ,

we let

f ∈ F  ⟺  ∀a ∈ A : f(a) ∈ F(a) .

For

F, G ∈ HOM(A, B) ,

we let

F ⊆ G  ⟺  ∀a ∈ A : F(a) ⊆ G(a) .

For any function F from HOM(A, B) we introduce the following notations:

• P(F) – the relative volume:

P(F) = _{a∈A}^{∏} \frac{| F(a) |}{| B |} ;

• H(F) – the entropy of F:

H(F) = − log P(F) .

• M(F) – the domain of F:

M(F) = {a | a ∈ A , F(a) ≠ B} .

It is easy to see, that

H(F) = _{a∈A}^{∑} log \frac{| B |}{| F(a) |} = _{a∈M(F)}^{∑} log \frac{| B |}{| F(a) |} .

If ϕ is some bijection from Hom(A_{1}, A_{2}), then we can define the mapping Φ such that

Φ : HOM(A_{2}, B) ⟶ HOM(A_{1}, B) ,
Φ(F) = ϕ ∘ F ,  where  ∀a ∈ A_{1} : (ϕ ∘ F)(a) = F(ϕ(a)) .

It is easy to check, that for any F, G from HOM(A_{2}, B) we have

P(Φ(F)) = P(F) , H(Φ(F)) = H(F) ,

ϕ(M(Φ(F)) = M(F) ,

∀f ∈ Hom(A_{2}, B) : f ∈ F ⟺ Φ(f) ∈ Φ(F) ,

F ⊆ G ⟺ Φ(F) ⊆ Φ(G) .

We will investigate the complexity of nondeterministic functions from HOM(A, B). We suppose, that in this case some coding algorithm for the sets A and B is fixed. We can suppose that

A ⊆ {0, 1}^{r} , r = ⌈log | A |⌉ ,
B ⊆ {0, 1}^{k} , k = ⌈log | B |⌉ .

Let S(x_{1}, x_{2}, ..., x_{r}) be a circuit with k outputs. By S(a) we denote the output sequence from {0, 1}^{k} on the input sequence a from {0, 1}^{r}.

The circuit S compute nondeterministic function F from HOM(A, B), if

∀a ∈ A : S(a) ∈ F(a) .

The complexity of the nondeterministic function F is minimal possible complexity of the circuits computing it. We denote the complexity of the function F by L(F).

In this paper we consider circuits built from elements with two inputs. We use circuit size as the complexity of circuits.

If R is a subsystem of HOM(A, B), then we define the Shannon function of R by:

L(R) = max_{F∈R} L(F) .

We will try to obtain bounds for the values

L(HOM_{ϵ}(A, B))  and  L(HOM^{m}(A, B)) ,

where

HOM_{ϵ}(A, B) = {F | F ∈ HOM(A, B) , P(F) ≥ ϵ} and
HOM^{m}(A, B) = {F | F ∈ HOM(A, B) , H(F) ≤ m} .

It is easy to see, that for ϵ = 2^{−m} we have

HOM^{m}(A, B) = HOM_{ϵ}(A, B) .

1.2 Previous and new results

This work is a natural development of the line of almost optimal circuit design. Shannon (1949) has put the problem and has obtained the first results in this direction. He defined the function L(n), the worst case complexity of n-variable boolean function, and has proved that

c_{1} \frac{2^{n}}{n} ≤ L(n) ≤ c_{2} \frac{2^{n}}{n} ,

for some positive constants c_{1} and c_{2}.

Lupanov(1956) has obtained that the asymptotic behavior of Shannon function is

L(n) ∼ \frac{2^{n}}{n} .

The research that followed has concentrated on the analysis of different classes of boolean functions, for example monotone function. Jablonsky(1957), Ugolnikov(1976), Pippenger(1978), Andreev(1988) has obtained interesting results in this area. Lupanov(1965) has developed local coding principle for this problem. Andreev(1985) has created stronger and more general method.

Nechiporuk(1965) has considered partial boolean functions. This is degenerate case of nondeterministic functions, i.e. the system HOM({0, 1}^{n}, {0, 1}). He has obtained the asymptotic for the Shannon function

L(HOM^{m}(\{0, 1\}^{n}, \{0, 1\})) ∼ \frac{m}{log m} .

in the case where the entropy m and the number 2^{n} are not very much different. Sholomov(1969) had proved this asymptotic behavior for more general case.

Pippenger(1977) has considered the classes of partial functions with fixed part of units in case of Nechiporuk(1965) restrictions for the domain size.

Andreev(1989) has proved the best result, namely

L (HOM^{m}(\{0, 1\}^{n}, \{0, 1\})) ∼ \frac{m}{log m} + O(n) ,

(no restrictions for domain size).

In this paper we consider the problem for the general case of nondeterministic functions. We prove that

L (HOM^{m}(A, U)) ∼ \frac{m}{log m} + O(n) .

for the sufficiently general case, when

log | U | = o(log m) .

This result has very strong applications in the area of algorithms derandomization. We discuss this connection in the next subsection.

1.3 Derandomization problem and nondeterministic functions complexity

One of the main problems of complexity theory is the derandomization problem, i.e. effective conversion of randomized algorithms to deterministic.

For this problem there are two main approaches. The first is effective computation of the number of units of boolean circuits. Luby and Velicovic (1991), Karpinsky and Luby (1993) have developed this approach.

The second way is effective construction of pseudorandom generators. Nisan(1990), Even, Goldreich and Luby (1992) have constructed some restricted pseudorandom generators.

Sipser (1986), Chor and Goldreich (1989), Linial, Luby, Saks and Zuckerman (1993) have investigated the problem of hitting sets, i.e. weak variant of pseudorandom generator.

A lot of randomized algorithms can be converted to deterministic ones, if we have an effective hitting set with certain parameters. This fact makes actual the problem of its construction.

The set Q is hitting set for the set system R if Q ∩ Z ≠ ∅ for any set Z from R.

Up to now there is no nontrivial results for general cases of all derandomization approaches. The hitting set problem has strong connection with complexity bounds for nondeterministic functions and below we discuss only this derandomization approach.

The main goal of this problematic is to construct effective hitting set for the system of sets with restricted complexity of its characteristic functions. As we have said earlier, there are no nontrivial results about such hitting set. This fact explains actuality of considerations of simpler set systems.

By E_{κ} we denote the set {0, 1, …, κ − 1}. For the sequence A = (A_{1}, A_{2}, ..., A_{n}) from (E_{κ}^{∗})^{n} we define the corresponding rectangle

N_{A} = A_{1} × A_{2} × ... × A_{n} .

By P(N_{A}) we denote the rectangle volume:

P(N_{A}) = n ; ∏ ; i=1 \frac{| A_{i} |}{| E_{κ} |} = n ; ∏ ; i=1 \frac{| A_{i} |}{κ} .

Let

I_{κ}(n, ϵ) = {N_{A} | A ∈ (E_{κ}^{∗})^{n} , P(N_{A}) ≥ ϵ} .

Nechiporuk (1965) has obtained the first result about hitting sets for the system I_{2}(n, ϵ), in connection with his research of partial boolean functions complexity. He had proposed deterministic algorithm with the working time 2^{O(n)}. This algorithm constructs for the system I_{2}(n, ϵ) hitting set with cardinality O(n/ϵ).

Sipser(1986) has proposed for this problem an algorithm which uses O(n) random bits. Chor and Goldreich(1989) have created an algorithm which uses 2n random bits.

The best result for the considered problem is obtained by Linial, Luby, Saks and Zuckerman (1993). They have proposed deterministic algorithm of a hitting set construction for the system I_{κ}(n, ϵ). The set cardinality and the algorithm working time are polynomial in κ(log n)/ϵ.

Let | A |= n and ϕ is bijection from Hom (A , {1, 2, ..., n}).We define the following mappings

Φ : (E_{κ})^{n}  ⟶  Hom(A, E_{κ}) ,
Φ^{∗} : I_{κ}(n)  ⟶  HOM(A, E_{κ}) ,

by the conditions

d = (d_{1}, d_{2}, ..., d_{n})  ⇒  Φ (d) (x) = d_{ϕ(x)} ,  x ∈ A ,
D = (D_{1}, D_{2}, ..., D_{n})  ⇒  Φ^{∗} (N_{D}) (x) = D_{ϕ(x)} ,  x ∈ A .

It is not difficult to check the following facts:

• Φ and Φ^{∗} are bijections;

• d ∈ N_{D}  ⟺  Φ(d) ∈ Φ^{∗}(N_{D}) ;
• N_{D} ⊆ N_{C}  ⟺  Φ^{∗}(N_{D}) ⊆ Φ^{∗}(N_{C}) ;

• P(N_{D}) = P(Φ^{∗}(N_{D})) .

In that way the mapping pair (Φ, Φ^{∗}) is a natural isomorphism between the systems

((E_{κ})^{n}, I_{κ}(n), ∈, ⊆, P)  and  (Hom(A, E_{κ}), HOM(A, E_{κ}), ∈, ⊆, P) .

It is easy to check, that

HOM_{ϵ}(A, E_{κ}) = Φ^{∗} (I_{κ}(n, ϵ)) .

In new terms the definition of the hitting set is the following: a set Q ⊆ Hom(A, B) is hitting for the system R ⊆ HOM(A, B), if

∀F ∈ R ∃f ∈ Q : f ∈ F .

By λ(R) we denote the minimal possible element number in the hitting sets for the system R.

By Hom_{l}^{compl}(A, U) we denote the set of all functions from Hom(A, U) with the complexity at most l. If

l ≥ L(HOM_{ϵ}(A, E_{κ})) ,

then the set Hom_{l}^{compl}(A, E_{κ}) is the hitting set for the system HOM_{ϵ}(A, E_{κ}).

For boolean case this fact was remarked independently in Krichevsky(1994) and Andreev(1994).

The size of the set Hom_{l}^{compl}(A, U) is at most the number of circuits with complexity l. Consequently the upper bound for Shannon function L(HOM_{ϵ}(A, E_{κ})) follows the bound of the hitting set size.

The construction of this hitting set includes consideration of all circuits with complexity l with conversion on each step of a circuit to the sequence of its values.

Our bounds of nondeterministic functions complexity offer a possibility to construct the small hitting set for the system I(n, ϵ). Its size is almost linear of (log n)/ϵ in the case

log κ = o (log log \frac{1}{ϵ}) .

We must remark, that trivial lower bound for the hitting set size is 1/ϵ.

In that way we obtain in significant case more strong result then Linial, Luby, Saks and Zuckerman (1993).

2 Complexity bounds for the worst case

2.1 Lower and preliminary upper bounds

Lemma 1 If

| A |≥ 2 , | U |≥ 2 ,

then

L (HOM^{m}(A, U)) ≤ 8 m | U | log | U | ,

and for any function F from HOM(A, U) it is true

L(F) ≤ O(1) | M(F) | log | U | .

Proof. We suppose, that

A ⊆ {0, 1}^{r} , r = ⌈log | A |⌉ .

Let F be some function from HOM^{m}(A, U). We will prove by | M(F) |- induction that

M(F) ≠ ∅  ⟹  L(F) ≤ (4 | M(F) | −3) (log | U | +1) .

If | M(F) |= 1, then evidently there exist constant function c from Hom(A, U) such that c ∈ F, consequently

L(F) ≤ L(c) ≤ ⌈log | U |⌉ ≤ (log | U | +1) .

We suppose that x_{1}, x_{2}, ..., x_{r} is the sequence of input variables. Let

A_{i,α} = {0, 1}^{i−1} × {α} × {0, 1}^{r−i} .

Suppose that | M(F) |≥ 2, then there exist variable x_{i} such that

M(F) ∩ A_{i,0} ≠ ∅ , M(F) ∩ A_{i,1} ≠ ∅ .

We define functions F_{0} and F_{1} from HOM(A, U) by the following way

F_{α}(b) = \{ \begin{matrix}F(b) & if b ∈ A_{i,α} \\ U & otherwise \end{matrix} , α ∈ \{0, 1\} .

It is easy to see, that

M(F) = M(F_{0}) ∪ M(F) , H(F) = H(F_{0}) + H(F_{1}) .

Let w be the selector function from Hom({0, 1} × U × U, U), i.e.

w(a, u_{1}, u_{2}) = \{ \begin{matrix}u_{1} & if a = 1 \\ u_{2} & if a = 0 \end{matrix} .

It is easy to see, that

L(w) ≤ 3⌈log | U |⌉ ≤ 3(log | U | +1) .

If f_{1} ∈ F_{1} and f_{0} ∈ F_{0}, then

w(x_{i}, f_{1}, f_{0}) ∈ F .

Consequently

L(F) ≤ L(F_{1}) + L(F_{0}) + L(w) .

For F_{1} and F_{0} the induction hypothesis is true, and we have

L(F) ≤ ((4 | M(F_{1}) | −3)(log | U | +1)) +
+ ((4 | M(F_{0}) | −3)(log | U | +1)) + 3(log | U | +1) =

= (4 | M(F) | −3)(log | U | +1) .

If ∅ ≠ V ⊆ U and V ≠ U then

log \frac{| U |}{| V |} ≥ log \frac{| U |}{| U | −1} ≥ \frac{1}{| U |} .

Consequently

H(F) ≥ _{a∈M(F)}^{∑} log \frac{| U |}{| F(a) |} ≥ _{a∈M(F)}^{∑} \frac{1}{| U |} = | M(F) | \frac{1}{| U |} ,

and we have

| M(F) | ≤ | U | H(F) ,

L(F) ≤ (4 | U | H(F) − 3)(log | U | +1) ≤ 8 | U | H(F)(log | U | . □

2.2 Nonconstructive upper bound for hitting set size

By Θ(x) we denote any nonnegative function such that

x → ∞ ⟹ Θ(x) = o(1) .

By HOM_{ϵ,ϕ}(A, U) we denote the following set

{F | F ∈ HOM_{ϵ}(A, U) , ∀a ∈ A : F(a) |=| U | −ϕ(a)} , and by Hom_{Σ,l}(A, E_{k}) the following

{ϕ | ϕ ∈ Hom(A, E_{k}) , _{a∈A}^{∑} ϕ(a) ≤ l} .

Lemma 2 If

| A |≥ 2 , | U |≥ 2 ,

then

log | HOM_{ϵ}(A, U) | ≤ (log | A | + log | U | +3) | U | log \frac{1}{ϵ} .

Proof. We let

| A |= n , | U |= k ,
ϕ ∈ Hom(A, E_{k}) , F ∈ HOM_{ϵ,ϕ}(A, U) .

We have

ϵ ≤ P(F) = _{a∈A}^{∏} \frac{| F(a) |}{k} = _{a∈A}^{∏} (1 − \frac{ϕ(a)}{k}) ≤

≤ _{a∈A}^{∏} exp (−\frac{ϕ(a)}{k}) = exp (−\frac{1}{k} _{a∈A}^{∑} ϕ(a)) .

Consequently

\frac{1}{ϵ} ≥ exp (\frac{1}{k} _{a∈A}^{∑} ϕ(a)) ,

_{a∈A}^{∑} ϕ(a) ≤ k ln \frac{1}{ϵ} .

In that way we have

ϕ ∈ Hom_{Σ,l}(A, E_{k}) , where l = ⌊k ln \frac{1}{ϵ}⌋ ,

and then

HOM_{ϵ}(A, U) ⊆ \begin{matrix}⋃ \\ ϕ ∈ Hom_{Σ,l}(A, E_{k}) \end{matrix} HOM_{ϵ,ϕ}(A, U) .  (1)

It is easy to check, that

log | HOM_{ϵ,ϕ}(A, U) | = log (_{a∈A}^{∏} ( \begin{matrix}k \\ ϕ(a) \end{matrix} )) ≤

≤ log (_{a∈A}^{∏} k^{ϕ(a)}) = (log k) _{a∈A}^{∑} ϕ(a) ≤

≤ (log k)l = log (k^{l}) .

By (1) for l ≥ 1 we have

| HOM_{ϵ}(A, U) | ≤ k^{l} | Hom_{Σ,l}(A, E_{k}) | ≤

≤ k^{l} ( \begin{matrix}n + l \\ n \end{matrix} ) = k^{l} ( \begin{matrix}n + l \\ l \end{matrix} ) ≤

≤ k^{l}(\frac{4(n + l)}{l})^{l} ≤ k^{l}(8n)^{l} .

In the case l = 0 this bound is true also.

□

Lemma 3 If

| A |≥ 2 , | U |≥ 2 ,

then

λ (HOM_{ϵ}(A, U)) ≤ (\frac{1}{ϵ})^{1+Θ(1/ϵ)}| U |^{1+Θ(|U|)} log | A | .

Proof. For any function F from HOM_{ϵ}(A, U) we have

\frac{| \{f | f ∈ Hom(A, U) , f ∈ F\} |}{| Hom(A, U) |} = P(F) ≥ ϵ .

Consequently, by the Nechiporuk (1965) way, we can construct by r steps the set Q_{r} such that

Q_{r} ⊆ Hom(A, U) , | Q_{r} |= r ,
| {F | F ∈ HOM_{ϵ}(A, U) , N_{F} ∩ Q_{r} = ∅} | ≤
(1 − ϵ)^{r} | HOM_{ϵ}(A, U) | ≤ e^{−ϵ r} | HOM_{ϵ}(A, U) | ,

where

N_{F} = {f | f ∈ Hom(A, U) , f ∈ F} .

We let

r = ⌈\frac{1}{ϵ} ln | HOM_{ϵ}(A, U) |⌉ ,

and obtain

| {F | F ∈ HOM_{ϵ}(A, U) , N_{F} ∩ Q_{r} = ∅} | < 1 .

Consequently for any function F from HOM_{ϵ}(A, U) we have

N_{F} ∩ Q_{r} ≠ ∅ .

By Lemma 2 we obtain

r ≤ \frac{1}{ϵ} ln | HOM_{ϵ}(A, U) | +1 ≤

≤ \frac{1}{ϵ} (ln | A | + ln | U | +3) | U | ln \frac{1}{ϵ} + 1 ≤

≤ (\frac{1}{ϵ})^{1+Θ(1/ϵ)}| U |^{1+Θ(|U|)} log | A | .

□

2.3 Main decomposition methods

Let

C = {0, 1}^{r} ,  A = {0, 1}^{p} ,  B = {0, 1}^{s} ,
r = p + s ,  p ≥ 1 ,  s ≥ 1 .  (2)

Let ϕ be some bijection from Hom(A × B, C) and ϕ^{−1} is inverse mapping from Hom(C, A × B). Let

ψ_{1} ∈ Hom(C, A) , ψ_{2} ∈ Hom(C, B) ,

and for all c from C

ϕ^{−1}(c) = (ψ_{1}(c), ψ_{2}(c)) .  (3)

If

F ∈ HOM(C, U) , D ∈ HOM(C, {0, 1}) ,
G ∈ HOM(A × B, U) , Q ∈ HOM(A, {0, 1}) ,

then by F |_{Q=α} we denote function from HOM(A × B, U) such that

G |_{Q=α}(a, b) = \{ \begin{matrix}G(a, b) & if Q(a) = α \\ U & otherwise \end{matrix} .

and by F |_{D=α} we denote function from HOM(C, U) such that

F |_{D=α}(c) = \{ \begin{matrix}F(c) & if D(c) = α \\ U & otherwise \end{matrix} .

Let w be the selector function from Hom({0, 1} × U × U, U) i.e.

w(a, u_{1}, u_{2}) = \{ \begin{matrix}u_{1} & if a = 1 \\ u_{2} & if a = 0 \end{matrix} .

Lemma 4 If for functions

F ∈ HOM(C, U) , Q ∈ HOM(A, {0, 1}) ,

it is true, that

Q(a) = {0, 1} ⟹ ∀b ∈ B : (ϕ ∘ F)(a, b) = U , then we have, that L(F) is at most

L ((ϕ ∘ F) |_{Q=1}) + L (F |_{(ψ_{1}∘Q)=0}) + L(Q) + L(ϕ^{−1}) + L(w) .

Proof. Let g_{1} be some function from Hom(A × B, U) and f_{0} some function from Hom(C, U), such that

g_{1} ∈ (ϕ ∘ F) |_{Q=1} ,  f_{0} ∈ F |_{(ψ_{1}∘Q)=0} ,  (4)

and q function from Hom(A, {0, 1}) such that q ∈ Q. We will check, that for any c from C the following condition is true

w (q(ψ_{1}(c)), g_{1}(ϕ^{−1}(c)), f_{0}(c)) ∈ F(c) .  (5)

Let

a = ψ_{1}(c) , b = ψ_{2}(c) ,

If Q(a) = 0 then we have

(ψ_{1} ∘ Q)(c) = Q(ψ_{1}(c)) = Q(a) = 0 ,

consequently

F |_{(ψ_{1}∘Q)=0}(c) = F(c)  and  f_{0}(c) ∈ F(c) .

In this case we have

w (q(ψ_{1}(c)), g_{1}(ϕ^{−1}(c)), f_{0}(c)) =
= w (0, g_{1}(ϕ^{−1}(c)), f_{0}(c)) = f_{0}(c) ∈ F(c) .

Consequently (5) is true.

Our condition is equivalent to the following

w (q(a), g_{1}(a, b), f_{0}(c)) ∈ (ϕ ∘ F)(a, b) ,  (6)

because

F(c) = (ϕ^{−1} ∘ ϕ ∘ F) (c) = (ϕ ∘ F) (ϕ^{−1}(c)) = (ϕ ∘ F)(a, b) .

If Q(a) = {0, 1}, then (ϕ ∘ F)(a, b) = U and (6) is true in any case. If Q(a) = 1, then

(ϕ ∘ F) |_{Q=1}(a, b) = (ϕ ∘ F)(a, b)

and consequently, by (4), we have

g_{1}(a, b) ∈ (ϕ ∘ F)(a, b) .

In this case we have also, that

w (q(a), g_{1}(a, b), f_{0}(c)) = w (1, g_{1}(a, b), f_{0}(c)) = g_{1}(a, b) ,

consequently (6) is true.

In that way we can compute the function F by the circuits from the figure 1. This fact implies necessary bounds for the complexity of the function F.

□

For G from HOM(A × B, U) we let

G_{a} ∈ HOM(A, U) , ∀b ∈ B : G_{a}(b) = G(a, b) .

We define also two other functions:

Q_{F,ϕ,A} ∈ HOM(A, {0, 1}) , C_{F,ϕ,A} ∈ HOM(A, U) ,

by the following way

Q_{F,ϕ,A}(a) = \{ \begin{matrix}\{0, 1\} & if M((ϕ ∘ F)_{a}) = ∅ \\ 1 & if | M((ϕ ∘ F)_{a}) |= 1 \\ 0 & if | M((ϕ ∘ F)_{a}) |≥ 2 \end{matrix} ,

C_{F,ϕ,A}(a) = _{b∈B}^{⋂} (ϕ ∘ F) |_{Q=1}(a, b) ,  where  Q = Q_{F,ϕ,A} .

We must check, that definition of the function C_{F,ϕ,A} is correct, i.e. for any a from A we have

_{b∈B}^{⋂} (ϕ ∘ F) |_{Q=1}(a, b) ≠ ∅ .

If Q(a) ≠ 1, then we have

∀b ∈ B : (ϕ ∘ F) |_{Q=1}(a, b) = U ,

and consequently

_{b∈B}^{⋂} (ϕ ∘ F) |_{Q=1}(a, b) = U .

If Q(a) = 1, then

| M((ϕ ∘ F)_{a}) | = 1  and  ∀b ∈ B : (ϕ ∘ F) |_{Q=1}(a, b) = (ϕ∘F)(a, b) .

Consequently in this case there exist element b_{a} from B such that

(ϕ ∘ F)(a, b_{a}) ≠ U , ∀b ∈ B , b ≠ b_{a} : (ϕ ∘ F)(a, b) = U ,

and we have

_{b∈B}^{⋂} (ϕ ∘ F) |_{Q=1}(a, b) = G(a, b_{a}) .

Lemma 5 It is true, that L(F) at most

L (C_{F,ϕ,A}) + L (F |_{ψ_{1}∘Q_{F,ϕ,A}=0}) + L (Q_{F,ϕ,A}) + L(ψ_{1}) + L(w) .

Proof. Let c be a function from Hom(A, U), such that c ∈ C_{F,ϕ,A}, then for any a from A and for any b from B we have

c(a) ∈ (ϕ ∘ F) |_{Q=1}(a, b) ,  (7)

(we suppose, that Q = Q_{F,ϕ,A}) because

c(a) ∈ C_{F,ϕ,A}(a) = _{q∈B}^{⋂} (ϕ ∘ F) |_{Q=1}(a, q) ⊆ (ϕ ∘ F) |_{Q=1}(a, b) .

Let

f_{0} ∈ F |_{ψ_{1}∘Q=0}  g_{1} ∈ (ϕ ∘ F) |_{Q=1} ,  q ∈ Q ,

then function F may be to compute by the circuit on Figure 1. In the correspondence with (7) we can suppose that

∀a ∈ A ∀b ∈ B : g_{1}(a, b) = c(a) .

In this case our circuit transforms into the circuit on the Figure 2 and we have necessary bound for the complexity of F.

□

2.4 Complexity of the functions with uniform entropy

By HOM_{A,ϵ}(A × B, U) we denote the set of all functions F from HOM(A × B, U) such that

∀a ∈ A : F_{a} ∈ HOM_{ϵ}(B, U) .

In this subsection we suppose, that

A = {0, 1}^{t} , t ≥ 1 ,  B = {0, 1}^{s} , s ≥ 1 ,  | U |≥ 2 , k = ⌈log | U |⌉ .

Lemma 6 If 1/2 ≤ ϵ, then L (HOM_{A,ϵ}(A × B, U)) at most

\frac{| A |}{log | A |} (1 + Θ (\frac{1}{ϵ}) + Θ(| A |)) ((log \frac{1}{ϵ}) + 2 log | U | +2 log log | B |) +

+ | B | | U |^{1+Θ(|U|)} (\frac{1}{ϵ})^{1+Θ(1/ϵ)} .

Proof. Let Q be some hitting set for the system HOM_{ϵ}(B, U), and F some function from HOM_{A,ϵ}(A × B, U). In this case

∀a ∈ A ∃q ∈ Q : q ∈ F_{a} ,

because for any a from A we have

F_{a} ∈ HOM_{ϵ}(B, U) .

Consequently there exists the function Ψ from Hom(A, Q) such that

∀a ∈ A : Ψ(a) ∈ F_{a} .

Let

p = ⌈log | Q |⌉ , P = {0, 1}^{p} .

In this case there exist functions Ψ_{1} and Ψ_{2} such that

Ψ_{1} ∈ Hom(A, P) ,  Ψ_{2} ∈ Hom(P, Q) ,  Ψ = Ψ_{1} ∘ Ψ_{2} .

We define a function Φ from Hom(P × B, U) by the following

∀α ∈ P ∀b ∈ B : Φ(α, b) = (Ψ_{2}(α)) (b) .

(Ψ_{2}(α) is function from Hom(B, U).) In this case we have

Φ(Ψ_{1}(a), b) = (Ψ_{2}(Ψ_{1}(a))) (b) = ((Ψ_{1} ∘ Ψ_{2})(a)) (b) =
= (Ψ(a))(b) ∈ F_{a}(b) = F(a, b) .

Consequently

∀a ∈ A , ∀b ∈ B : Φ(Ψ_{1}(a), b) ∈ F(a, b) ,

and we can compute the function F by the circuit on Figure 3. It is easy, that

L(F) ≤ L(Ψ_{1}) + L(Φ) .

Because

Ψ_{1} ∈ Hom(A, P) = Hom ({0, 1}^{t}, {0, 1}^{p}) ,
Φ ∈ Hom(P × B, U) ⊆ Hom ({0, 1}^{p+s}, {0, 1}^{k}) ,

then by Lupanov (1965) bounds we have

L(Ψ_{1}) ≤ \frac{2^{t}}{t}(1 + Θ(t))p ≤ \frac{2^{t}}{t}(1 + Θ(t))

((log \frac{1}{ϵ}) (1 + Θ (\frac{1}{ϵ})) + (log | U |)(1 + θ(| U |) + log log | B |) ≤

\frac{| A |}{log | A |} (1 + Θ (\frac{1}{ϵ}) + Θ(| A |)) (log \frac{1}{ϵ} + 2 log | U | +2 log log | B |) ,

(8)

because, by Lemma 3,

p = log | P | ≤ (1 + Θ (\frac{1}{ϵ})) log \frac{1}{ϵ} + (1+Θ(| U |)) | U | + log log | B | .

By analogical way we have

L(Φ) ≤ \frac{2^{p+s}}{p + s}(1 + Θ(p + s))k ≤ O(1) | B | \frac{log | U |}{log | B | + log | Q |} | Q | ≤

≤ O(1) | B | \frac{log | U |}{log | B | + log | Q |}(\frac{1}{ϵ})^{1+Θ(1/ϵ)}| U |^{1+Θ(|U|)} log | B | ≤

≤ | B | (\frac{1}{ϵ})^{1+Θ(1/ϵ)}| U |^{1+Θ(|U|)} .  (9)

The sum of (8) and (9) is the necessary bound.

□

2.5 Uniform mapping classes

Let

| A | = | B | , H ⊆ Hom(A, B) .

The set H of mappings is uniform class, if any mapping from H is a bijection and for any different a_{1}, a_{2} from A and for any different b_{1}, b_{2} from B we have

| \{J | J ∈ H , J(a_{1}) = b_{1} , J(a_{2}) = b_{2}\} | = \frac{| H |}{| A | (| A | −1)} .

Such classes of mappings has been considered in Markovsky, Carter and Wegman (1978) and in Carter and Wegman (1979). In this subsection we obtain some new results about such function classes.

By R_{+} we denote the set of all nonnegative real numbers. If J is some function from Hom(A, R_{+}) and S ⊆ A then we let

Σ_{S}J = _{a∈S}^{∑} J(a) ,

Σ_{S}^{(2)}J = ∑ ; \begin{matrix}a, b ∈ S \\ a ≠ b \end{matrix} J(a) J(b) .

Lemma 7 If H is an uniform class, and

H ⊆ Hom(A × B, C) ,  | A |≥ 2 , | B |≥ 2 ,  (10)

then for any function J from Hom(C, R_{+}) there exists mapping ψ from H such that

_{a∈A}^{∑} Σ_{\{a\}×B}^{(2)} ψ ∘ J ≤ \frac{1}{| A |} Σ_{C}^{(2)} J .

Proof. If

a ∈ A , b_{1}, b_{2} ∈ B , b_{1} ≠ b_{2} ,

then, because H is uniform class, we have

_{ϕ∈H}^{∑} (ϕ ∘ J)(a, b_{1}) · (ϕ ∘ J)(a, b_{2}) = _{ϕ∈H}^{∑} J(ϕ(a, b_{1})) · J(ϕ(a, b_{2})) =

∑ ; \begin{matrix}c_{1}, c_{2} ∈ C \\ c_{1} ≠ c_{2} \end{matrix} | \{ϕ | ϕ ∈ H , ϕ(a, b_{1}) = c_{1} , ϕ(a, b_{2}) = c_{2}\} | J(c_{1}) J(c_{2}) =

= ∑ ; \begin{matrix}c_{1}, c_{2} ∈ C \\ c_{1} ≠ c_{2} \end{matrix} \frac{| H |}{| C | (| C |)} J(c_{1}) J(c_{2}) = \frac{| H |}{| C | (| C | −1)} Σ_{C}^{(2)} J .

Consequently

_{ϕ∈H}^{∑} _{a∈A}^{∑} Σ_{{a}×B}^{(2)} ϕ ∘ J =

= _{a∈A}^{∑} ∑ ; \begin{matrix}b_{1}, b_{2} ∈ B \\ b_{1} ≠ b_{2} \end{matrix} _{ϕ∈H}^{∑} (ϕ ∘ J)(a, b_{1}) · (ϕ ∘ J)(a, b_{2}) =

= _{a∈A}^{∑} ∑ ; \begin{matrix}b_{1}, b_{2} ∈ B \\ b_{1} ≠ b_{2} \end{matrix} \frac{| H |}{| C | (| C | −1)} Σ_{C}^{(2)} J =

= | A | (| B | (| B | −1)) \frac{| H |}{| A || B | (| A || B | −1)} Σ_{C}^{(2)} J =

= \frac{| H | (| B | −1)}{| A || B | −1} Σ_{C}^{(2)} J ≤ \frac{| H |}{| A |} Σ_{C}^{(2)} J .

In that way we have

\frac{1}{| H |} _{ϕ∈H}^{∑} (_{a∈A}^{∑} Σ_{\{a\}×B}^{(2)} ϕ ∘ J) ≤ \frac{1}{| A |} Σ_{C}^{(2)} J .

Our Lemma follow from this bound.

□

Lemma 8 If H is uniform class and (10), then for any function J from Hom(A, R_{+}) there exists mapping ψ from H such, that

_{a∈A}^{∑} (Σ_{\{a\}×B} ψ ∘ J − \frac{1}{| A |} Σ_{C} J)^{2} ≤ Σ_{C} J^{2} ,

_{a∈A(t)}^{∑} Σ_{\{a\}×B} ψ ∘ J ≤ (\frac{1}{t^{2}} \frac{1}{| A |} Σ_{C} J + \frac{1}{t}) Σ_{C} J^{2} ,

where

A(t) = \{a | a ∈ A , Σ_{\{a\}×B} ψ ∘ J ≥ \frac{1}{| A |}Σ_{C} J + t\} .

Proof. We will consider the mapping ψ, wich exists by previous Lemma. In this case we have

_{a∈A}^{∑} (Σ_{\{a\}×B} ψ ∘ J − \frac{1}{| A |} Σ_{C} J )^{2} =

_{a∈A}^{∑} (Σ_{\{a\}×B} (ψ ∘ J)^{2} + Σ_{\{a\}×B}^{(2)} ψ ∘ J + \frac{1}{| A |^{2}}(Σ_{C} J )^{2}−

− 2 (Σ_{\{a\}×B} ψ ∘ J) \frac{1}{| A |} Σ_{C} J ) =

= Σ_{A×B} (ψ ∘ J)^{2} + _{a∈A}^{∑} Σ_{\{a\}×B}^{(2)} ψ ∘ J + \frac{1}{| A |}(Σ_{C} J )^{2} −

− 2 (Σ_{A×B} ψ ∘ J) \frac{1}{| A |} Σ_{C} J =

= Σ_{C} J^{2} + _{a∈A}^{∑} Σ_{\{a\}×B}^{(2)} ψ ∘ J − \frac{1}{| A |} (Σ_{C} J)^{2} ≤

≤ Σ_{C} J^{2} + \frac{1}{| A |} Σ_{C}^{(2)} J − \frac{1}{| A |} (Σ_{C} J)^{2} =

= (1 − \frac{1}{| A |}) Σ_{C} J^{2} ≤ Σ_{C} J^{2} .

In the following we have also the sequence of transformations.

_{a∈A(t)}^{∑} Σ_{{a}×B} ψ ∘ J =

= _{a∈A(t)}^{∑} \frac{1}{| A |}Σ_{C} J + _{a∈A(t)}^{∑} (Σ_{\{a\}×B} ψ ∘ J − \frac{1}{| A |}Σ_{C} J ) ≤

≤ _{a∈A(t)}^{∑} \frac{(Σ_{\{a\}×B} ψ ∘ J − \frac{1}{|A|}Σ_{C} J )^{2}}{t^{2}} \frac{1}{| A |} Σ_{C} J +

+ _{a∈A(t)}^{∑} \frac{(Σ_{\{a\}×B} ψ ∘ J − \frac{1}{|A|}Σ_{C} J )^{2}}{t} =

= (\frac{1}{t^{2}} \frac{1}{| A |}Σ_{C} J + \frac{1}{t}) _{a∈A(t)}^{∑} (Σ_{\{a\}×B} ψ ∘ J − \frac{1}{| A |}Σ_{C} J )^{2} ≤

= (\frac{1}{t^{2}} \frac{1}{| A |}Σ_{C} J + \frac{1}{t}) _{a∈A}^{∑} (Σ_{\{a\}×B} ψ ∘ J − \frac{1}{| A |}Σ_{C} J )^{2} ≤

= (\frac{1}{t^{2}} \frac{1}{| A |}Σ_{C} J + \frac{1}{t}) Σ_{C} J^{2} .

□

Lemma 9 If H is uniform class and (10), then for any function J from Hom(A, {0, 1}) there exists mapping ψ from H such, that

_{a∈D}^{∑} Σ_{\{a\}×B} ψ ∘ J ≤ \frac{1}{| A |} (Σ_{C} J)^{2} ,

where

D = {a | a ∈ A , Σ_{{a}×B} ψ ∘ J > 1} .

Proof. We have

Σ_{\{a\}×B}^{(2)} ψ ∘ J = ( \begin{matrix}Σ_{\{a\}×B} ψ ∘ J \\ 2 \end{matrix} ) ,

Σ_{C}^{(2)} J = ( \begin{matrix}Σ_{C} J \\ 2 \end{matrix} ) ≤ \frac{1}{2} (Σ_{C} J)^{2},

because the function J from Hom(A, {0, 1}). If a ∈ D we have

Σ_{{a}×B} ψ ∘ J ≤ 2 Σ_{{a}×B}^{(2)} ψ ∘ J .

Below we suppose, that ψ is a function from Lemma 7. Then we have

_{a∈D}^{∑} Σ_{{a}×B} ψ ∘ J ≤ _{a∈D}^{∑} 2 Σ_{{a}×B}^{(2)} ψ ∘ J ≤

≤ _{a∈A}^{∑} 2 Σ_{\{a\}×B}^{(2)} ψ ∘ J ≤ 2 \frac{1}{| A |} Σ_{C}^{(2)} J ≤ \frac{1}{| A |} (Σ_{C} J)^{2},

□

Let A and B are copies of the Galua Field GF(q). By HL(A, B) we denote the set of all ϕ from Hom(A, B) such that for some x ≠ 0 and y from GF(q) this mapping is possible to represent in the following way

ϕ(a) = x · a + y .

It is easy to see, that

| Hom(A, B) | = | A | (| A | −1) ,

and, how it was proved in Carter and Wegman (1979), this class is uniform. It is true, because for any different a_{1}, a_{2} from A and for any different b_{1}, b_{2} from B the system

\{ \begin{matrix}x · a_{1} + y = b_{1} \\ x · a_{2} + y = b_{2} \end{matrix}

has only one solution.

2.6 Complexity of the functions with big entropy

We suppose, that conditions (2) and (3) are satisfied. Let

F ∈ HOM(C, U) , G = ϕ ∘ F ,

and t is a real number at least 1. By A(F, ϕ, t) we denote the set of all a from A such that

H(G_{a}) ≥ \frac{H(F)}{| A |} + t .

Let d_{F,ϕ,t} be the characteristic function of the set A(F, ϕ, t), i.e.

d_{F,ϕ,t} ∈ Hom(A, \{0, 1\}) , d_{F,ϕ,t}(a) = \{ \begin{matrix}1 & if a ∈ A(F, ϕ, t) \\ 0 & otherwise \end{matrix}

Lemma 10 If the following conditions are true

H(F) ≤ m , | C |^{2/3} ≤ m ≤| C | log | U | ,

2 \frac{m}{log m} ≤ | A | ≤ 4 \frac{m}{log m} , \frac{log | U |}{log | C |} ≤ 1 ,

t = (log m)^{3/4} (log | U |)^{1/4} ,  (11)

then we have

L ((ϕ ∘ F) |_{d_{F,ϕ,t}=0}) ≤ | U |^{O(1)} | C |^{3/4+Θ(|C|)} +

+ \frac{m}{log m} (1 + Θ(| C |) + O(1)(\frac{log | U |}{log m})^{1/4}) .

Proof. Let

ϵ = exp_{2} (−\frac{m}{| A |} − t) , G_{0} = (ϕ ∘ F) |_{d_{F,ϕ,t}=0} .

In this case

G_{0} ∈ HOM_{A,ϵ}(A × B, U) .

Consequently we can obtain a bound for its complexity by applying Lemma 6. We have that L(G_{0}) is at most

\frac{| A |}{log | A |} (1 + Θ (\frac{1}{ϵ}) + Θ(| A |)) (log \frac{1}{ϵ} + 2 log | U | +2 log log | B |) +

+ | B | | U |^{1+Θ(|U|)} (\frac{1}{ϵ})^{1+Θ(1/ϵ)} .  (12)

By the applying (11), we obtain

≤ \frac{m}{| A |} + t = \frac{m}{| A |} (1 + t \frac{| A |}{m}) ≤

\frac{m}{| A |} (1 + log m^{3/4} log | U |^{1/4} (4 \frac{m}{log m}) \frac{1}{m}) =

= \frac{m}{| A |} (1 + 4 (\frac{log | U |}{log m})^{1/4}) .

In that way we have

log \frac{1}{ϵ} ≤ \frac{m}{| A |} (1 + 4 (\frac{log | U |}{log m})^{1/4}) .

and then

\frac{1}{ϵ} ≤ exp_{2} (log m (\frac{1}{2} + 2 (\frac{log | U |}{log m})^{1/4}))  (13)

because | A | ≥ 2m/ log m. Also by (11) we have

| B | = \frac{| C |}{| A |} ≤ | C |^{1/3+Θ(|C|)} ,

log log | B | ≤ log log | C | ≤ (1 + Θ(m)) log log m .

Also it is true

log m ≤ (1 + Θ(m)) log | A | .

Combining this bounds with (12) we have that L(G_{0}) is at most

\frac{| A |}{log m}(1 + Θ(m))·

· (\frac{m}{| A |} (1 + 4 (\frac{log | U |}{log m})^{1/4}) + 2 log | U | +3 log log m) +

+ | B | | U |^{1+Θ(|U|)}·

· exp_{2} ((log m) (\frac{1}{2} + 2 (\frac{log | U |}{log m})^{1/4}) (1 + Θ(m)))  (14)

By using of the bound

\frac{m}{| A |} ≥ \frac{1}{2} log m ,

we obtain

(\frac{m}{| A |} (1 + 4 (\frac{log | U |}{log m})^{1/4}) + 2 log | U | +3 log log m) ≤

≤ \frac{m}{| A |} (1 + O(1) (\frac{log | U |}{log m})^{1/4} + Θ(m))  (15)

If

\frac{log | U |}{log m} ≤ (\frac{1}{32})^{4} ,

then, by (13), we have

\frac{1}{ϵ} ≤ exp_{2} ((log m) (\frac{1}{2} + 2 (\frac{log | U |}{log m})^{1/4}) (1 + Θ(m))) ≤

≤ m^{9/16+Θ(m)} .

But if

\frac{log | U |}{log m} > (\frac{1}{32})^{4} ,

then

(\frac{log | U |}{log m})^{1/4} ≤ O(1) (\frac{log | U |}{log m}) ,

and we obtain, that

\frac{1}{ϵ} ≤ exp_{2} ((log m) (\frac{1}{2} + 2 (\frac{log | U |}{log m})^{1/4}) (1 + Θ(m))) ≤

≤ m^{1/2+Θ(m)} | U |^{O(1)} .

Consequently in any case we have

| B | | U |^{1+Θ(|U|)} exp_{2} ((log m) (\frac{1}{2} + 2 (\frac{log | U |}{log m})^{1/4}) (1 + Θ(m))) ≤

≤ \frac{| C |}{| A |} m^{9/16+Θ(m)} | U |^{O(1)} ≤

≤ \frac{| C |}{| A |} | A |^{9/16+Θ(|A|)} | U |^{O(1)} ≤

≤ \begin{matrix}| C | & 1+Θ(|C|) \\ | A | & 7/16 \end{matrix} | U |^{O(1)} ≤ \begin{matrix}| C | & 1+Θ(|C|) \\ (| C |^{2/3}) & 7/16 \end{matrix} | U |^{O(1)} ≤

≤ | C |^{3/4+Θ(|C|)} | U |^{O(1)} .

By using bounds (14) and (15), we obtain the necessary bound.

□

Lemma 11 If the conditions (11) are true, then there exists a mapping ϕ from HL(A × B, C) such that

H ((ϕ ∘ F) |_{d_{F,ϕ,t}=1}) ≤ m (\frac{3}{2}\sqrt{\frac{log | U |}{log m}}) .

Proof. Let J be the function from Hom(C, R_{+}) such that

J(a) = log \frac{| U |}{| F(a) |} .

Then we have

Σ_{C} J = H(F) ≤ m ,
Σ_{C} J^{2} ≤ Σ_{C} (J log | U |) ≤ m log | U | .

By Lemma 8 there exists a mapping ϕ from HL(A × B, C) such that

_{a∈S(t)}^{∑} Σ_{\{a\}×B} (ϕ ∘ J) ≤ (\frac{1}{t^{2}} \frac{m}{| A |} + \frac{1}{t}) m log | U | ,  (16)

where

S(t) = \{a | a ∈ A , Σ_{\{a\}×B}(ϕ ∘ J) ≥ \frac{m}{| A |} + t\} .

In the following we suppose, that

G = ϕ ∘ F , G_{1} = G |_{d_{F,ϕ,t}=1} ,

We have, that

H(G_{a}) = _{b∈B}^{∑} log \frac{| U |}{| G_{a}(b) |} = _{b∈B}^{∑} log \frac{| U |}{| G(a, b) |} =

= _{b∈B}^{∑} log \frac{| U |}{| F(ϕ(a, b)) |} = _{b∈B}^{∑} J(ϕ(a, b)) = Σ_{\{a\}×B} (ϕ ∘ J) .

Consequently the sets A(F, ϕ, t) and S(t) are equal and from (16) we have

_{a∈A(F,ϕ,t)}^{∑} Σ_{\{a\}×B} (ϕ ∘ J) ≤ (\frac{1}{t^{2}} \frac{m}{| A |} + \frac{1}{t}) m log | U | .

It is easy that

H(G_{1}) = _{a∈A}^{∑} H((G_{1})_{a}) =

= _{a∈A(F,ϕ,t)}^{∑} H((G_{1})_{a}) + _{a∈A\A(F,ϕ,t)}^{∑} H((G_{1})_{a}) =
= _{a∈A(F,ϕ,t)}^{∑} H(G_{a}) ,

because

(G_{1})_{a} = \{ \begin{matrix}G_{a} & if a ∈ A(F, ϕ, t) \\ ≡ U & if a ∈ A \ A(F, ϕ, t) \end{matrix} ,

and the entropy of the function ≡ U is equal to 0. Consequently

H(G_{1}) ≤ (\frac{1}{t^{2}} \frac{m}{| A |} + \frac{1}{t}) m log | U | .

By (11), we have

H(G_{1}) ≤ (((log m)^{−3/2}(log | U |)^{−1/2}) ((1/2) log m) +
+ (log m)^{−3/4}(log | U |)^{−1/4}) m log | U | =

(\frac{1}{2} (\frac{log | U |}{log m})^{1/2} + (\frac{log | U |}{log m})^{3/4}) m ≤ \frac{3}{2} (\frac{log | U |}{log m})^{1/2} m .

□

Lemma 12 If

C = \{0, 1\}^{n} ,  | C |≥ 2  , | U |≥ 2 ,  \frac{log | U |}{log | C |} ≤ \frac{1}{2} ,

l = \frac{3}{2}(\frac{log | U |}{log m})^{1/2} m ,

then

L(HOM^{m}(C, U)) ≤ \frac{m}{log m} (1 + Θ(| C |) + O(1)(\frac{log | U |}{log | C |})^{1/4}) +

+ O(1)| C |^{3/4+Θ(|C|)} | U |^{O(1)} + L(HOM^{l}(C, U)) .

Proof. If m ≤ | C |^{3/4}, then our Lemma is true evidently. And in the following we suppose, that m < | C |^{3/4}.

Let F be some function from HOM^{m}(C, U). We apply Lemma 4 to this function. We suppose, that d = d_{F,ϕ,t} and conditions (11) are true.

By Lemma 4 and Lupanov (1965) bounds we have

L(F) ≤ L ((ϕ ∘ F) |_{d=1}) + L ((ϕ ∘ F) |_{d=0}) +

+ \frac{| A |}{log | A |}(1 + Θ(| A |)) + O(1) log^{2} | C | + O(1) log | U | ≤

≤ L ((ϕ ∘ F) |_{d=1}) + L ((ϕ ∘ F) |_{d=0}) +
+ Θ(m)\frac{m}{log m} + Θ(| C |)| C |^{3/4} + Θ(| U |) | U | .  (17)

By Lemma 11 we have

H ((ϕ ∘ F) |_{d=1}) ≤ \frac{3}{2} m (\frac{log | U |}{log m}) ,

consequently

≤ L ((ϕ ∘ F) |_{d=1}) ≤ L(HOM^{l}(C, U) .

By combining this bound with (17) and with Lemma 10 bound for L ((ϕ ∘ F) |_{d=0}) we obtain necessary result.

□

Lemma 13 If

A = \{0, 1\}^{n} ,  | A |≥ 2  , | U |≥ 2 ,  \frac{log | U |}{log | A |} ≤ \frac{1}{2} ,

then

L(HOM^{m}(A, U)) ≤ \frac{m}{log m} (1 + Θ(| A |) + O(1)(\frac{log | U |}{log | A |})^{1/4}) +

+ O(1)| A |^{3/4+Θ(|A|)} | U |^{O(1)} .

Proof. Let

m(k) = (\frac{3}{2} (\frac{log | U |}{log | A |}))^{k} m .

By Lemma 12 we have

L(HOM^{m(k)}(A, U)) ≤ \frac{m(k)}{log m(k)} (1 + Θ(| A |) + O(1)(\frac{log | U |}{log | A |})^{1/4}) +

+ O(1)| A |^{3/4+Θ(|A|)} | U |^{O(1)} + L(HOM^{m(k+1)}(A, U)) . (18)

By the iteration of this bound we obtain

L(HOM^{m}(A, U)) ≤

≤ ( k ; ∑ ; i=1 \frac{m(k)}{log m(k)}) (1 + Θ(| A |) + O(1)(\frac{log | U |}{log | A |})^{1/4}) +

+ k O(1)| A |^{3/4+Θ(|A|)} | U |^{O(1)} + L(HOM^{m(k+1)}(A, U)) . We suppose that m ≤| A | log | U |, because

max_{F∈HOM(A,U)} H(F) = | A | log | U | .

We change minimal k such that m(k + 1) ≤ | A |^{3/4} . In our conditions we have

\frac{3}{2} (\frac{log | U |}{log | A |})^{1/2} ≤ \frac{3}{2} (\frac{1}{4})^{1/2} = \frac{3}{4} < 1 ,

consequently

k ≤ O(1) log \frac{| A | log | U |}{| A |^{3/4}} ≤ O(1) log | A | ,

k ; ∑ ; i=1 \frac{m(k)}{log m(k)} ≤ \frac{m}{log m} (1 + Θ(| A |) + O(1)(\frac{log | U |}{log | A |})^{1/2}) .

By combining this bound with (18) we obtain the necessary result.

□

2.7 General case

We suppose, that conditions (2) and (3) are true.

Lemma 14 If the following conditions are true

H(F) ≤ m , 2 ≤ m ≤| C | log | U | ,

1 ≤ \frac{| A |}{m | U |^{4} log^{4} m} ≤ 2 , \frac{log | U |}{log | C |} ≤ 1 ,

then there exists a mapping ϕ from HL(A × B, C) such that

L (F |_{ψ_{1}∘Q_{F,ϕ,A}=0}) + L (Q_{F,ϕ,A}) ≤ Θ(m)\frac{m}{log m} .

Proof. We define the function J from Hom(C, {0, 1}) by the following

J(c) = \{ \begin{matrix}1 & if F(c) ≠ U \\ 0 & otherwise \end{matrix} .

We suppose, that

F_{0} = F |_{ψ_{1}∘Q_{F,ϕ,A}=0} ,
D = {a | a ∈ A , Σ_{{a}×B} ϕ ∘ J > 1} .

Earlier we have defined the function Q_{F,ϕ,A} such that

Q_{F,ϕ,A}(c) = 0 ⟺ c ∈ D ,

consequently

| M(F_{0}) | = _{a∈D}^{∑} Σ_{{a}×B} ϕ ∘ J .

We suppose, that for the function ϕ assumption of Lemma 9 is true. In this case we have

| M(F_{0}) | ≤ \frac{1}{| A |}(Σ_{C} J)^{2} = \frac{1}{| A |}(| M(F) |)^{2}

We has noticed in Lemma 1 that

| M(F) | ≤ H(F) | U | .

Consequently

| M(F_{0}) | ≤ \frac{1}{| A |}m^{2}| U |^{2} ≤ \frac{m^{2}| U |^{2}}{m | U |^{4} log^{4} m} = \frac{m}{| U |^{2} log^{4} m} .

In that way we have, that

H(F_{0}) ≤ | M(F_{0}) | log | U | ≤ \frac{m log | U |}{| U |^{2} log^{4} m} .

We apply Lemma 1 for the function F_{0} and obtain the following bound for its complexity

L(F_{0}) ≤ 8 H(F_{0}) | U | log | U | ≤
≤ \frac{m log^{2} | U |}{| U | log^{4} m} ≤ \frac{2m}{log^{4} m} = Θ(m)\frac{m}{log m} .  (19)

It is easy to see, that for the complexity of any boolean function f from Hom(A, {0, 1}) the following bound is true

L(f) ≤ O(1) | {a | a ∈ A , f(a) = 0} | log | A | .

By the construction we have

| \{a | a ∈ A , Q_{F,ϕ,A}(a) = 0\} | ≤ | M(F_{0}) | ≤ \frac{m}{| U |^{2} log^{4} m}

Consequently

L(Q_{F,ϕ,A}) ≤ \frac{m log | A |}{| U |^{2} log^{4} m} ≤ O(1) \frac{m}{log^{3} m} = Θ(m) \frac{m}{log m} .

We combine this bound with the bound (19) and obtain the necessary result.

□

Theorem 1 If | C |≥ 2 , | U |≥ 2 , then

L(HOM^{m}(C, U)) ≥ \frac{m}{log m} (1 − Θ(m)) + O(1) log | C | ,

L(HOM^{m}(C, U)) ≤ \frac{m}{log m} (1 + Θ(m) + O(1)(\frac{log | U |}{log m})^{1/4}) +
+ O(1) log(| C |) + | U |^{O(1)} .

Proof. The lower bound can be obtained analogical by to Sholomov (1969).

At the first step we suppose, that C = {0, 1}^{r} and r ≥ 2. We can suppose without loss of generality that

m ≥ 2 , \frac{log | U |}{log m} ≤ \frac{1}{2} ,

because in other case our theorem follow from Lemma 1. Let F be some function from HOM(C, U). We have, that

H(F) ≤ | C | log | U | ,

Consequently we can suppose also, that

m ≤ | C | log | U | .

We choosee the sets A and B such that

A = {0, 1}^{p} , B = {0, 1}^{s} ,  p ≥ 1 , s ≥ 1 ,  p + s = r ,
1 ≤ \frac{| A |}{m | U |^{4} log^{4} m} ≤ 2 ,  (20)

It is impossible only in the case when

m | U |^{4} log^{4} m ≥ \frac{1}{4} | C | .

In this case our theorem follow immediately from Lemma 13 and we suppose, that (20) is true.

We compute our function F according to Lemma 5. We have that L(F) is at most

L (C_{F,ϕ,A}) + L (F |_{ψ_{1}∘Q_{F,ϕ,A}=0}) + L (Q_{F,ϕ,A}) + L(ψ_{1}) + L(w) .

It is easy to see, that

L(w) ≤ O(1) log | U | .  (21)

The function ψ_{1} is some boolean linear (r, p)-operator. Consequently according to Lupanov (1956) bounds for matrix complexity we have

L(ψ_{1}) ≤ \frac{rp}{log r} + O(r) = \frac{log | C | log | A |}{log log | C |} + O(1) log | C | =
Θ(m)\frac{m}{log m} + O(1) log | C | .  (22)

From Lemma 14 we have that there exists a mapping ϕ from HL(A × B, C) such that

L (F |_{ψ_{1}∘Q_{F,ϕ,A}=0}) + L (Q_{F,ϕ,A}) ≤ Θ(m)\frac{m}{log m} .  (23)

It is easy to see, that

C_{F,ϕ,A} ∈ HOM^{m}(A, U) ,

consequently by applying Lemma 13 to this function we have

L(C_{F,ϕ,A}) ≤ \frac{m}{log m} (1 + Θ(| A |) + O(1)(\frac{log | U |}{log | A |})^{1/4}) +

+ O(1)| A |^{3/4+Θ(|A|)} | U |^{O(1)} ≤
≤ \frac{m}{log m} (1 + Θ(m) + O(1)(\frac{log | U |}{log m})^{1/4}) + | U |^{O(1)} . (24)

The sum of (21), (22), (23), (24) is the necessary bound.

In the following we do not suppose that C = {0, 1}^{r}. Let

C ⊆ D = {0, 1}^{r} , 2^{r−1} <| C |≤ 2^{r} .

Let F be some function from HOM^{m}(A, U). We define a function G from HOM(D, U) such that

G(c) = \{ \begin{matrix}F(c) & if c ∈ C \\ U & otherwise . \end{matrix}

It is easy to see, that

H(G) = H(F) , G ∈ HOM^{m}(D, U) .

Also it is easy, that some circuit S compute the function G if and only if this circuit compute the function F. Consequently L(G) = L(F) , and we have, that

L(HOM^{m}(C, U)) ≤ L(HOM^{m}(D, U)) .

It is not difficult to check, that necessary bounds are true, because

| C | ≤ | D | ≤ 2 | C | .
□

3 Hitting set construction

3.1 The case of not too small entropy

By N we denote the set of all natural numbers.

Lemma 15 There exists a function l(n, k, p, q) from Hom(N^{4}, N) computable in the time polynomial of

log n + log k + log p + log q , such that

L(HOM_{p/q}(A, U)) ≤ l(| A |, | U |, p, q) ,

and l(n, k, p, q) at most

\frac{log(q/p)}{log log(q/p)} (1 + Θ (\frac{q}{p}) + O(1)(\frac{log k}{log log(q/p)})^{1/4}) + O(1) log n + k^{O(1)} .

Proof. This fact follow from the proof of Theorem 1.

□

By Hom_{p,q}^{hit}(A, U) we denote the set of all functions f from Hom(A, U) such that

L(f) ≤ l(| A |, | U |, p, q) .

Lemma 16 The set Hom_{p,q}^{hit}(A, U) is a hitting set for the system HOM_{p/q}(A, U). If

Θ(| A |) log \frac{q}{p} ≥ log | A | log log | A | ,
log | U | ≤ Θ(| A |) log log(q/p) ,  (25)

then

| Hom_{p,q}^{hit}(A, U) | ≤ (\frac{q}{p})^{1+Θ(|A|)} .

Proof. It is easy to see, that Hom_{p,q}^{hit}(A, U) is a hitting set. Let

| A |= n ,  | U |= k ,  l = l(n, k, p, q) .

It easy to see, that our bound is at most NS(⌈log n⌉, ⌈log k⌉, l), i.e. the number of circuits with ⌈log n⌉ inputs, ⌈log k⌉ outputs and with complexity at most l. Lupanov (1965) has proved that this number is at most

(O(1)(log n + l))^{l+log k+O(1)} .

From this bound and conditions (25) we obtain, that

log NS(⌈log n⌉, ⌈log k⌉, l) ≤ (1 + Θ(n)) log \frac{q}{p} .

Consequently the necessary bound is true.

□

3.2 Hash classes of functions

In this section we are constructing the classes of the special hash mappings. Let A and B finite sets. Let S be a subset of A.

We say that mapping ϕ from Hom(A, B) is hash function for S, if

a_{1}, a_{2} ∈ S , a_{1} ≠ a_{2}  ⟹  ϕ(a_{1}) ≠ ϕ(a_{2}) .

Let F be a mapping set, F ⊆ Hom(A, B). The set F is hash class for the set S, if in F there exists some hush function for S.

The set F is μ-hash class, if it is hash class for any μ-elements subset of A.

Such function classes has been considered in Poljak, Pultr and Rodl (1983) and in Krichevsky (1985). In this subsection we construct special μ-hash class for our goals.

Let

F_{1} ∘ F_{2} = {ϕ_{1} ∘ ϕ_{2} | ϕ_{1} ∈ F_{1} , ϕ_{2} ∈ F_{2}}

for

F_{1} ⊆ Hom(A, B) , F_{2} ⊆ Hom(B, C) .

By GF(q) we denote the q-elements Galua field. For a natural η ≥ 2 and g ∈ GF(q) we let

ϕ_{η,g} ∈ Hom(GF(q)^{η}, GF(q)) ,
ϕ_{η,g}(a_{1}, a_{2}, ..., a_{η}) = a_{1} + a_{2}g + a_{3}g^{2} + ... + a_{η}g^{η−1} ,
LF_{η}(G) = {ϕ_{η,g} | g ∈ G} , G ⊆ GF(q) .

The following Lemma 17 and Lemma 18 has been proved by Krichevsky (1985).

Lemma 17 If

| G | ≥ ( \begin{matrix}μ \\ 2 \end{matrix} ) (η − 1) + 1 , η ≥ 2 ,

then LF_{η}(G) is μ-hash class.

Lemma 18 If

F_{1} ⊆ Hom(A, B) , F_{2} ⊆ Hom(B, C) ,

are μ-hash classes, then

F_{1} ∘ F_{2} ⊆ Hom(A, C)

is μ-hash class also. Lemma 19 For any finite sets A, B and natural numbers μ, η, such that

| A |≥ | B |≥ μ^{2}η , η ≥ 2 , μ ≥ 1 ,

there exists μ-hash class Hom_{μ,η}^{hash}(A, B) such that Hom_{μ,η}^{hash}(A, B) ⊆ Hom(A, B) ,

| Hom_{μ,η}^{hash}(A, B) | ≤ μ^{2}η (\frac{log | A |}{⌊log | B |⌋})^{1+2 log μ/ log η} .

There exist an algorithm for this class construction with working time at most

| Hom_{μ,η}^{hash}(A, B) | | A |^{1+o(1)} .

Proof. We have

2 (( \begin{matrix}μ \\ 2 \end{matrix} ) (η − 1) + 1) − 1 =

= μ^{2}η − μ^{2} − μ(η − 1) + 1 ≤ μ^{2}η ≤ | B | .

Consequently, if we let d = ⌊log | B |⌋ then

( \begin{matrix}μ \\ 2 \end{matrix} ) (η − 1) + 1 ≤ 2^{d} ≤ | B | .  (26)

Let s minimal nonnegative integer number such that

| A | ≤ exp_{2}(d η^{s}) , where exp_{2}(x) = 2^{x} . (27)

Let

C_{i} = GF(exp_{2}(d η^{i})) , i = 0, 1, ..., s .

In this case we may suppose that

C_{i+1} = (C_{i})^{η} , i = 0, 1, ..., s − 1 .

By (26) there exist sets G_{i}, such that

G_{i} ⊆ C_{i} ,  | G_{i} | = ( \begin{matrix}μ \\ 2 \end{matrix} ) (η − 1) + 1 ,  (28)

i = 0, 1, ..., s − 1 .

According to Lemma 17 the function sets

LF_{η}(G_{i}) ⊆ Hom(C_{i+1}, C_{i}) , i = 0, 1, ..., s − 1 ,

are μ-hash classes. Let

Hom_{μ,η}^{hash}(C_{s}, C_{0}) = LF_{η}(G_{s−1}) ∘ LF_{η}(G_{s−2}) ∘ ... ∘ LF_{η}(G_{0}) .

By Lemma 18 we have, that this function set is μ-hash class. By (28) we have the following upper bound for the class size

| Hom_{μ,η}^{hash}(C_{s}, C_{0}) | ≤ s−1 ; ∏ ; i=0 | G_{i} | ≤ (μ^{2}η)^{s} .  (29)

By (27) we have that

s = ⌈\frac{log \frac{log|A|}{d}}{log η} ⌉ ≤ \frac{log \frac{log|A|}{⌊log|B|⌋}}{log η} + 1 ,

(μ^{2}η)^{s} ≤ μ^{2}η exp (\frac{(2 log μ + log η)}{log η} log \frac{log | A |}{⌊log | B |⌋}) =

= μ^{2}η (\frac{log | A |}{⌊log | B |⌋})^{1+2 log μ/ log η} .

Consequently, by (29),

Hom_{μ,η}^{hash}(C_{s}, C_{0}) ≤ μ^{2}η (\frac{log | A |}{⌊log | B |⌋})^{1+2 log μ/ log η} .

We let

Hom_{μ,η}^{hash}(A, B) = {ϕ} ∘ Hom_{μ,η}^{hash}(C_{s}, C_{0}) ∘ {ψ} ,

where ϕ some injection from Hom(A, C_{s}) and ψ some injection from Hom(C_{0}, B).

The upper bound for algorithm working time is trivial.

□

3.3 The case of small entropy

Lemma 20 If Q ⊆ Hom(B, U) is a hitting set for the system HOM_{ϵ}(B, U) and F ⊆ Hom(A, B) is ⌊| U | log \frac{1}{ϵ}⌋-hash function class, then the set F ∘Q is hitting for the set system HOM_{ϵ}(A, U).

Proof. Let F be some function from HOM_{ϵ}(A, U). We know, that

| M(F) | ≤ μ(ϵ) ,  where  μ(ϵ) = ⌊| U | log \frac{1}{ϵ}⌋ .

Let a mapping ϕ from F be hash function for M(F). There exists such hash function, because the set F is μ(ϵ)-hash class. By ϕ and F we define new function G such that

G ∈ HOM(B, U) , G(b) = _{a∈ϕ^{−1}(b)}^{⋂} F(a) .

This definition is correct because ϕ is hash function for the set M(F) and consequently in this case for any x from B it is true

| M(F) ∩ ϕ^{−1}(b) | ≤ 1 .  (30)

We have, that

| M(G) | = | M(F) | , H(G) = H(F) .

consequently

G ∈ HOM_{ϵ}(B, U) .

Because Q is hitting set for the system HOM_{ϵ}(B, U) , there exist some function g from Q such that g ∈ G. We consider

f = ϕ ∘ g ∈ F ∘ Q ,

and will be checking that f ∈ F. It means, that

∀a ∈ A : f(a) ∈ F(a) .  (31)

Let a ∈ A, b = ϕ(a). If F(a) = U, then (31) is true for any value of f(a). Suppose, that F(a) ≠ U. Then, in the correspondence with function G definition, and (30) we have

∀x ∈ ϕ^{−1}(b) \ {a} : F(x) = U .

Consequently

G(b) = _{x∈ϕ^{−1}(b)}^{⋂} F(x) = F(a) ,

and we have

f(a) = (ϕ ∘ g)(a) = g(ϕ(a)) = g(b) ∈ G(b) = F(a) ,
f(a) ∈ F(a) .
□

In the following we suppose

n =| A | ,  k =| U | ,  μ = ⌊k log \frac{q}{p}⌋ ,
η = μ^{log log log log n} , θ = ⌈log(μ^{2}η)⌉ .

Hom_{p,q}^{hit∗}(A, U) = \{ \begin{matrix}Hom_{p,q}^{hit}(A, U) if θ ≥ \sqrt{log n} \\ Hom_{μ,η}^{hash}(A, \{0, 1\}^{θ}) ∘ Hom_{p,q}^{hit}(\{0, 1\}^{θ}, U) \\ if θ < \sqrt{log n} \end{matrix}

Theorem 2 The set Hom_{p,q}^{hit∗}(A, U) is a hitting set for the system HOM_{p/q}(A, U). If

log | U | ≤ Θ(| A |) log log(q/p) ,  (32)

then

| Hom_{p,q}^{hit∗}(A, U) | ≤ (\frac{q}{p} log | A |)^{1+Θ(|A|)} .

There exists a algorithm for this set construction with the working time at most

| A |^{1+o(1)} (\frac{log | A |}{p/q})^{1+o(1)}

Proof. Suppose that θ ≥ \sqrt{log n}. In this case we have

θ ≤ 2 log μ + log η ≤ (1 + o(1)) log μ log log log log n , consequently

log μ ≥ (1 − o(1)) \frac{\sqrt{log n}}{log log log log n} ≥ (log n)^{1/4} .

By (32) we have

(log n)^{1/4} ≤ log μ ≤ (1 − Θ(n)) log log \frac{q}{p} ,
Θ(n) log \frac{q}{p} ≥ log n log log n ,

and necessary result follows from Lemma 16.

Consider the second case: θ < \sqrt{log n}. The set Hom_{p,q}^{hit∗}(A, U) is hitting by Lemma 19 and Lemma 20.

We will be considering two subcases:

μ > log log log n  and  μ ≤ log log log n .

In the first subcase

log θ log log θ ≤ (1 + Θ(n)) ((log η) + 2 log μ)^{2} ≤

≤ (1 + Θ(n)) log^{2} η ≤ (1 + Θ(n)) (log log log log n log μ)^{2} ≤

≤ (1 + Θ(n)) (log log μ log μ)^{2} ≤ Θ(n)μ = Θ(n) log \frac{q}{p} .

Consequently by the Lemma 16 we have

| Hom_{p,q}^{hit}(\{0, 1\}^{θ}, U) | ≤ (\frac{q}{p})^{1+Θ(n))} .  (33)

By the bounds of the Lemma 19 we have

| Hom_{μ,η}^{hash}(A, {0, 1}^{θ})) | ≤ μ^{2}η (log n)^{1+2(log μ)/ log η} ≤
≤ μ^{2+log log log log n}(log n)^{1+Θ(n)} ≤ μ^{2+log μ}(log n)^{1+Θ(n)} ≤
≤ (\frac{q}{p})^{Θ(n)}(log n)^{1+Θ(n)} .  (34)

By multiplication (33) and (34) we have necessary bound. In the second subcase also by Lemma 19 we have the following bounds

| Hom_{μ,η}^{hash}(A, {0, 1}^{θ})) | ≤ μ^{2}η (log n)^{1+2 log k/ log m} ≤

≤ (log log log n)^{2+log log log log n}(log n)^{1+Θ(n)} ≤ (log n)^{1+Θ(n)} . (35)

It is easy to see, that in this subcase

| Hom_{μ,η}^{hash}(A, {0, 1}^{θ})) | ≤ | Hom(A, {0, 1}^{θ})) | ≤
≤ k^{(2^{θ})} ≤ (μ + 1)^{μ+1} = (log n)^{Θ(n)} .  (36)

By multiplication (35) and (35) we have necessary bound.

□

Acknowledgments

The author thanks V.B.Kudrjavcev, A.A.Bolotov (Moscow university) and S.Skyum, S.Soloviev (Aarhus university) for very helpful discussions.

References

[1] Shennon, C.E. (1949), The synthesis of two-terminal swiching circuits, Bell. Syst. Tech. J. 28, pp.59-98.

[2] Jablonsky, S.V. (1957), About of classes of boolean functions with small complexity, Uspekhi Mat. Nauk 12, pp.1273-1276. (In Russian) Inglish translation in Russian Math. Surveys.

[3] Lupanov, O.B. (1956) About gating and contact-gating circuits, Dokl. Akad. Nauk SSSR 111, pp.1171-11744. (In Russian), English translation in Soviet Math. Docl.

[4] Lupanov, O.B. (1965) About a method circuits design – local coding principle, Problemy Kibernet. 10, pp.31-110. (in Russian). English Translation in Systems Theory Res. v.10, 1963.

[5] Nechiporuk, E.I. (1965), About the complexity of gating circuits for the partial boolean matrix, Dokl. Akad. Nauk SSSR 163, pp.40-42. (In Russian). English translation in Soviet Math. Docl.

[6] Sholomov, L.A. (1969) About realization of partial boolean functions by circuits from functional elements, Problemy Kibernet. 21, pp.215-226. (in Russian). English Translation in Systems Theory Res. v.21, 1971.

[7] Ugolnikov, A.B. (1976), Circuit design for monotone functions, Problemy Kibernet. 31, pp.167-185. (in Russian). English Translation in Systems Theory Res. v.21, 1971.

[8] Pippenger, N. (1977) Information theory and the complexity of Boolean functions, Math. Systems Theory 10, pp.129-167.

[9] Pippenger, N. (1978), The complexity of monotone boolean functions, Math. Systems Theory 11, pp.289-316.

[10] Andreev, A.E. (1985) A universal principle of self-correction, Mat. Sb. 127(169), pp.147-172.(In Russian), English translation in Math. USSR-Sb. 55, pp.145-169.

[11] Andreev, A.E. (1988), Circuit design in full monotone basis, Matem. Voprosy Kibernet. 1, pp.114-139. (In Russian).

[12] Andreev, A.E. (1989), On the complexity of the realization of partial Boolean functions by circuits of functional elements, Diskret. mat. 1, pp.36-45. (In Russian). English translation in Discrete Mathematics and Applications 1, pp.251-262.

[13] Andreev, A.E.(1994), Almost optimal hitting set. Dokl. Akad. Nauk RUSSIA (accepted).

[14] Krichevsky, R.E. (1994), Occam’s Razor, Partially Specified Boolean Functions, String Matching, and Independent Sets, Inform. and Comput. 108, pp.158-174.

[15] Nisan, N. (1990), Pseudo-random generators for space-bounded computation, in “Proceedings of 22th ACM Symposium on Theory of Computation,” pp.204-212.

[16] Sipser, M. (1986), Expanders, Randomness or Time vs. Space, in “Proceedings of 1th conference on Structure in Complexity Theory”, Lecture Notes in Computer Science 223, pp.325-329.

[17] Chor, B., and Goldreich, O. (1989), On the power of Two-Point Based Sampling, J. Complexity 5, pp.96-106.

[18] Luby, M., and Velickovic, B. (1991), On deterministic approximation of DNF, in “Proceedings of 23th ACM Symposium on Theory of Computation,” pp.430-438.

[19] Even, G., Goldreich, O., Luby, M., Nisan, N., and Velickovic, B. (1992), Approximation of general independent distributions, in “Proceedings of 24th ACM Symposium on Theory of Computation,” pp.10-16.

[20] Linial, N., Luby, M., Saks, M., and Zuckerman, D. (1993), Efficient construction of a small hitting set for combinatorial rectangles in high dimension, in “Proceedings of 25th ACM Symposium on Theory of Computation,” pp.258-267.

[21] Karpinski, M., and Luby, M. (1993), Approximating the number of solutions to a GF(2) Formula, J. Algorithms, 14, pp.280-287.

[22] Markowsky, G., Carter, J.L., and Wegman, M.N. (1978) Analysis of a universal class of hash functions, Lecture Notes in Computer Science 64, pp.345-354.

[23] Carter, J.L., and Wegman, M.N. (1979) Universal Classes of Hash Functions, J. Comput. System Sci. 18, pp.143-154.

[24] Poljak,, S., Pultr, A., and Rodl V. (1983), On qualitatively independent partitions and related problems, Discrete Appl. Math. 6, pp.193-205.

[25] Krichevsky, R.E. (1985), Optimal hashing, Inform. and Control 62, pp.64-92.

Figures

[figure: w; q; g_{1}; f_{0}; ϕ^{−1}; ψ_{1}; ψ_{2}]

Figure 1

[figure: w; q; c; f_{0}; ψ_{1}]

Figure 2

[figure: Φ; Ψ_{1}; a ∈ A; b ∈ B; α ∈ P; c ∈ C; α = Ψ_{1}(a); c = Φ(α, b)]

Figure 3

Recent Publications in the BRICS Report Series

RS-94-1 Glynn Winskel. Semantics, Algorithmics and Logic: Basic Research in Computer Science. BRICS Inaugural Talk. February 1994, 8 pp.

RS-94-2 Alexander E. Andreev. Complexity of Nondeterministic Functions. February 1994, 47 pp.

RS-94-3 Uffe H. Engberg and Glynn Winskel. Linear Logic on Petri Nets. February 1994, 54 pp.

RS-94-4 Nils Klarlund and Michael I. Schwartzbach. Graphs and Decidable Transductions based on Edge Constraints. February 1994, 19 pp. Appears in: Trees in Algebra and Programming CAAP ’94 (ed. S. Tison), LNCS 787, 1994.

RS-94-5 Peter D. Mosses. Uni�ed Algebras and Abstract Syntax. March 1994, 21 pp. To appear in: Recent Trends in Data Type Speci�cation (ed. F. Orejas), LNCS 785, 1994.

RS-94-6 Mogens Nielsen and Christian Clausen. Bisimulations, Games and Logic. April 1994, 37 pp. Full version of paper to appear in: New Results and Trends in Computer Science, LNCS, 1994.