Learning Disjunction of Conjunctions

1 . Introduction

The ability of humans to learn new concepts is remarkable and mysterious . Little progress has been made in the problem of simulating this process by computer . Worse still there is little agreement on what realistic specifications of the desired behavior of such a simulation might look like . The approach taken to this problem in a previous paper [13) was to appeal to computational complexity theory to provide some guidelines on this last question. In particular, various classes of prop­ ositional concepts were explored that could be learned from examples, or sometimes oracles, in a polynomial number of computational steps. Pre­ sumably biological systems cannot l earn classes that are computationally intractable .

The overall model was hierarchical. A concept to be learned was expressed as a propositional expression in terms of concepts already known . If this expression was too complex it was computation­ ally infeasible to learn it . The maximal complex­ ity of such expressions that could be learned feasibly was studied.

That investigation pointed to one particular concept class that especially warranted further investigation--those that could be expressed as a

*Supported in part by National Science Foundation grant MCS - 83- 02385 .

LEARNING DISJUNCTIONS OP CONJUNCTIONS

L.G. Valiant

Aiken Computation Laboratory Harvard University Cambridge, 11A 02138

disjunction of conjunctions, called disjunctive normal form (DNF) . The attraction of this class is that humans appear to like it for representing knowledge as is evidenced, for example , by the success of the production system paradigm [6) and of Horn clause logics [8) . Our investigations sug­ gest that significantly larger classes may not be learnable in polynomial time. Hence this class may turn out to have a central rol·e.

This paper is organized as follows . In Sec­ tion 2 the formal framework will be described first. It will then be shown that significant sub­ classes of propositional DNF expressions can be learned in polynomial time just from examples . Whether the whole class can be so learned remains an open problem.

The section following that will discuss how the above results can be extended to allow vari­ ables and relations in the manner of predicate calculus. The extension is to a very r estricted part of the predicate calculus where there is only exist ential quantification and a limited number of variables .

In Section 4 the question as to whether the above algorithm can be made robust to errors in the data is discussed . It is shown that the learning algorithms can indeed be made robust to a small rate of even maliciously constructed errors.

The suitability of our learning algorithms to implementations on distributed "bra in- like" models of computation is the subject of Section 5 . In the propositional case , under certain natural restric­ tions, such implementations are immediate, but this does not appear to extend to the case allowing r e ­ lations .

Finally in Section 6 we observe that the limits of learnability are not far off . Even if it is known that a single purely conjunctive expression explains fifty percent of the occurrences of a con­ cept, discovering or approximating this conjunction may be NP- hard .

The word learning has been used in numerous senses in philosophy , psychology and AI . A useful distinction to make in this context is whe ther the available data from which the learning or induction is to be made is consistent with many varied hypoth­ esis, or essentially with just one . In the former situation, which is often tacitly accepted in the philosophy of science, and also in machine learning

(e.g. [5]), the learning problem is ill-defined because of lack of information, and the best one can hope for i s to select , with good taste, from among the several plausible hypotheses. In con­ trast , in the latte r situa tion, sufficient informa­ tion is available in the data and the only problem is to deduce the hypothesis from it computation­ ally . Our current work is directed at the latter situation and is motivated by the observation that distinct human individuals appear to converge remarkably to essentially the same notions about familiar concepts .

The technical idea that makes our positive results possible is the probabilistic method of specification. We assume that positive and negative examples of concepts are drawn from certain prob­ ability distributions that are determined by the real world, but are otherwise arbitrary and possibly unknown . The task of the l earning procedure is to discover a recognition algorithm for the concept that gives the correc t answer with high probability on further examples drawn from the same distribu­ tion .

The main assumption made by our methodology as outlined in [13] is that useful classes of learnable concepts can have simple mathematical characteriza­ tions . Although we believe that DNF expressions constitute a good and relevant knowledge representa­ tion , we don ' t wish to make this an equally central assumption . Alternative c lasses may be also worth exploring, such as those cons ide r ed in [13].

As a philosophi cal note we observe that our probabi listic specification of learning has partic­ u l ar effective ness in certain extreme empiricist or p r ocedurist worlds. Suppose that the world is too complex t o model but intelligent systems manage to cope using simple strategies (c.f. [11]). Then specify ing how these strategies achieve their goals may be too complex to describe and consequently programming or discovering these strategies may be very difficult. In our mode l the simple strategies correspond to the recognition algorithms. The com­ plex world is captured by the distribution, which need never be described . The important point is that the e ffi ciency of our learning procedures is limited only by the complexity of the algorithm to be l earned and not by the complexity of the distri­ bution, which may indeed by arbitrarily complex with no ill e ffect . We conclude that in such worlds learning may have a n unexpectedly central role that cannot be replaced by programming (c.f. Simon [12]) .

2 . Propositional DNF Expressions

We shall first introduce the terminology we use which is consistent with [13] . Let {p 1 , ·.· , pt} be a set of Boolean predicates. Let l'lo be the set of all 3t monomials (or conjuncts) over these predicates . A monomial is any product obtained by ~hoosing for each i (1 ~i ~t) whe ther Pi or Pi or neithe r should appear in it, and conjoining ~hes~ choices . Thus if t ~ 4 then p 1 p 3 and P1P 2 P4 are typical members of M 0 ·

Let F be a Boolean function over {p 1 , .·. , pt} . More formally F is a mapping from {O ,l}t +{0 ,1} that specifies for each combination of truth values of the t arguments p 1 , ·.· , pt of F whether F is false or true. To allow for incompletely defined inputs we shall extend F to the domain {O,l,*}t according to the following rule : For v E {O,l,*}t F(v) =1 iff F(v') =1 for all v ' E{o,l}t such that v and v ' agree on all components on which v is defined (i.e., equals 0 or 1). For example if F(l,O,O) =1 and F(l,O,l) =1 then we define F(l,O,*) =1. If either F(l,O,O) or F(l,O,l) were 0 then F(l,O,*) would be 0. Such an exten­ sion of a function we call the concept F. The criterion of truth of the concept for an incom­ pletely defined input v is whether the defined components of v are sufficient to guarantee the truth of the associated function F.

For each concept F we define two probability distributions o+ and D on its positive and negative examples . The positive examples are the vectors vE {O,l,*}t such that F(v) =1. On this set o- (v) = 0 and o+ (v) ~0. The sum I: o+ (v) equals one when summed over this set. Similarly the negative examples are the vectors v E {O ,l,*}t such that F(v) =0. On this second set o+(v) = 0 and D-(v) ~0 . The sum I: D-(v) equals one when summed over this set.

We define two procedures that generat e posi­ tive and negative examples randomly from their re­ spective distributions. A call of EXAMPLES+ will generate a vector v E {O ,l,*}t such that F(v) =l where each such v has probability o+(v) of being produced at each call. A call of EXAMPLES- will generate a vector v such that F(v) =0 where each such v has probability D-(v) of being pro­ duced. Each call of these procedures is probabi ­ listically independent of each other call .

A disjunctive no~al fo~ (DNF) expression f is an expression

where M =.M 0 · Thus f set of the monomial set is the disjunction of a sub­ Mo.

Since M 0 is of size exponential in t and we will be interested in expressions that can be con­ structed in polynomial time, we shall need to dis­ cuss subclasses of M 0 that are of only polynomial sizeo

Definition. A set M 1 cM 0 is polynomial generable dete~inistically (p.g.d.) iff there is a determin­ istic algorithm that in time polynomial in t ter­ minates and generates descriptions of all the mem­ bers of ~1 1 ·

Example 2.1. For any positive integer k the class M(k) of monomials consisting of k or fewer predi­ cates (negated or not) is p.g.d.

It would appear to be more flexible, and hence advantageous in practice, if the monomial set were not so constrained, a priori, but were to be deduced from calls of EXM1PLES+ or EXM1Pl£S- for the given concept F . This is feasible if appropriate condi­ tions hold for the distributions, such as the fol­ lowing:

Definition. Di~tributions {n+,n- } have poZynomiaZZy generabZe monom~az sets (p.g . m.s . ) if there is an ~lgo:ithm that can call EXM1PLES+ and EXAUPLES-, runs 1n t1me polynomial in t and h , anc generates a set M1=M 0 of monomials that with probability at least (1- h- 1 ) has the following property:

where summation is over every v such that v 'fm for any m EHp [N.B . In "v ~m" 1 as elsewhere, v and m are identified with Boolean functions in the obvious way. Thus v ~m means that the truth values defined in v make m true.]

The motivation for this last definition is to justify certain strategies for finding an M that would otherwise appear to be unjustified heuiistics .

Example 2.2 . Suppose that for some small parameter A ~0 we called EXAMPLES+ a certain number of times and put into M 1 every monomial that appears as a submonomial of the positive examples with frequency at least A. For some distributions this set would be exponentially large . For certain others, which one could define , the set would be only polynomially large .

Example 2 . 3. A good practical possibility might be to let M 1 be the intersection of some 11 (k) of Example 2 . 1 with the set gene rated in Example 2.2. For example if we choose k = 3 and A = 0 then the monomial set is simply all conjuncts of sets of up to three predicates that are ever satisfied simulta­ neously in some positive example .

The quantitative aspects of our learning strat­ egies are captured by the function L(h , S): Suppose we have an urn containing a large number (possibly infinite) of marbles of at most s kinds . We want to sample a number x of marbles (with replacement) so that with probability at least 1 - h-1 the sam­ ple is such that if a furthe r marble is picked at random then the probability that this new marble is not already represented in the previous sample is less than h - l In [13] it is shown that there is a function . L (h , S) ,;; 2h (S +loge h) that is an upper bound on th1s x for all possible relative fre­ quencies of the S kinds of marbles .

. Our basic results about learning DNF expres­ Slons from examples alone will be expressed with respect to our previous definitions of a concept F(pl ·····Ptl having distributions n+ , D- where F =:L mi with summation over some M =1-10 . It is essent1ally the dual of Theorem A in ]13] .

Theorem 2 . 1. There is an algorithm E calling EXM·1PLES+ and EXM1PLES- such that (i) whether M =11l for some M1 that is p . g.d. or (ii) whethe r {n+ , n- } has a p.g. m. s., E will generate a DNF formula g in time polynomial in h and t that will have probability at l east (1 - h-1) of having each of the following properties:

and

[In case (i) EXM1PLES + is not necessary and the sum :L n+ in (a) is zero.]

Proof . Algorithm E is simply the following:

Generate M 1 [in case (i) determinis­ tically, in case (ii) prob­ abilistically to have the desired properties]; L+L(h, IMlll; For i + 1 to L do begin v EXAMPLES-; For all m EM1 s.t. v~m M 1 +Ml -m;

end

end

To verify (a) we note that in case (i) the monomials of F consist only of members of M and will always be contained in the monomial set o¥ g . Hence g(v) =O~F(v) =O ~n+(v) =0. In case (ii) some monomi als of F will be missing from g be­ cause t?e~ ~ere already missing from M 1 · But by the def1n1t1on of p . g.m. s . the probability :L n+(v) summed over all v such that v 'fm for any m E M 1 , is bounded by h-1 with probability at least 1 - h - 1 · Hence :L n+(v) summed over v such that g(v) =0 is bounded by the same quantity.

To show (b) suppose to the contrary that the sum :L D- (v) is at least h - 1 . Suppose we consider each m EM 1 that is not a monomial of F to be a marble and that a call of v+EXAMPLES- is inter­ preted as taking a sample of at least one marble, (i . e. the submonomials of v cannot be monomials of F) . Then after L(IM1 i , hl such calls with probability at least (1 - h-1) the set of monomials in M 1 that are not in F and have not been chosen have total probability of occurrence

Algorithms in the style of algorithm E are natural in several contexts in inductive inference [2] . In the current context it is made noteworthy by its provably good behavior for aZZ distributions .

3. DNF Expressions with Relations

In AI applications there is often need for referring to several distinct objects and to ex­ pressing relationships among them. For sheer expressive power the full predicate calculus is very useful, of course, but it clearly includes much power , such as arbitrary alternations of quantifiers, that are little used. It is an interesting question to delineate the minimal part of the predicate cal­ culus that is still expressive enough for conven­ tional AI applications. Only a few attempts have been made in this direction [4].

Here we are concerned with the question of how much the class of expressions that is learnable can be extended to allow relations without sacrificing polynomial time learnability. We shall now allow object variables x 1 , .·. ,xr· Instead of proposi­ tional predicates we will allow relation predicates p 1 , .·. , pt each of which has a number, its arity, that def~nes the number of arguments it has. A monomial is now an existentially quantified con­ junction of relational predicates, such as:

For notational brevity the existential quantifica­ tion will be suppressed.

This notation is sufficient to express a predi­ cate on a scene that depends on the existence of certain subobjects in the scene that obey certain relations among themselves.

For a fixed r and a fixed set of predicates p 1 , ·.· ,pt we can define the class Mo of all mono­ mials that can be formed from then in the obvious way. We regard two monomials are identical iff they can be obtained from each other by permuting the variable names.

Definition. A set M 1 ~M 0 is polynomial generable deterministically (p.g.d.) iff there is a determin­ istic algorithm that in time polynomial in t and r terminates and generates all the members of M 1 .

Example 3.1. For any fixed numbers r and k the set of monomials consisting at most k predicates , negated or not, is p.g.d. In fact there are no more than (2r+lt)k of themo

In tre ating the probabilistic generation of monomials from examples a problem would arise if we had to relate the variables {xi} to the primitive input vectors {v }. In the case under consideration, however , this whole problem can be comp l etely finessed. Let D+, D- be probability distributions on the positive and negative examples of the primi­ tive input vectors {v} . We extend D+, D- to the domain of monomials M 0 as follows: D+(m) is the probability that the conjunctive relation m holds for a random output v of EXN1PLES+. Similarly for D-.

Definition. Distributions {D+,D- } have polynomially generably monomial sets (p.g.moso) if there is an algorithm calling EXAMPLES+ and E~WLES- that runs in time polynomial in h, t and r and generates a set M1 sMo of monomials that with probability at least (1 -h-1 ) has the following property:

where summation is over every v such that v~m for any m E M 1 [i.e., as in the propositional case the monomials of F missing from M1 account for a small fraction of the probability space {v}. Now, however, v~m has the complex meaning that the monomial expression m is true of primitive input v.].

Examples 3.2 and 3.3. The analogues of Examples 2.2 and 2 . 3 can be defined in the obvious way.

Theorem 3.1. The statement and proof are identical t~those of Theorem 2.1 except that the monomial set M has the more general interpretation allow­ ing relations. o

In summary, the learning algorithm we are suggesting, if we use Example 3.3 with A =0 as the monomial set, is the following: List all mono­ mials with up to r object variables and k predi­ cates, that hold in at least one observed positive example. Eliminate from this list all monomials that occur in some observed negative example. Take the disjunction of the remaining monomials as the desired expr ession.

4. Robustness

How much tolerance to erroneous data should we require of a learning system? On the one hand experience suggests that learning is difficult enough from error-free data and becomes well nigh impossible if the data is seriously flawed . This suggests the possibility that the learning phenom­ enon is only feasible with very low error rates. On the other hand some robustness is clearly essen­ tial and it is reasonable to investigate the maximum error rate that can be compensated for.

In this section we will modify Algorithm E and show that the modified form Algorithm E*, is resis­ tant to a quantifiable, if low, error rate, whether in the propositional or extended relational case of Section 3.

Definition. If A is an oracle then we say that oracle B is "oracle A with e rror rate 8" if at each call of B (i) with probability 1- 8 it calls oracle A correctly, and (ii) with proba­ bility 8 it produces an arbitrary answer possibly chosen maliciously by an adversary .

The modified a lgorithm that has access only to an oracle "EXAMPLES"'" with error rate 6 (t,h)" will now perform T (I 111 I ,h) cycles and will depend on a parameter E(t,h), where 6 , E and T are related below. Z is an integer array indexed by the mem­ bers of M 1 and initialized to zero. Algorithm E* is the following:

end and end The following analogue to Theorems 2 . 1 and 3 . 1 can be proved . We shall restrict ourselves to the deterministic case . The other case , when M1 has p . g . m. s., can be treated similarly by detecting any maliciously generated monomials having too many submonomials by their low frequency of occurrence. Thus the result refers to an arbitrary function F that can be expressed as the sum of monomials from H 1 ·

Theorem 4.1 . There is an algorithm E* calling EXN-lPLES- with error rate 8 = (4hJH 1 JJ - 1 that will generate a DNF formula g in time polynomial in h and t such that with probability at least (1 - h - 1) g has the following properties

Proof. We will show that the described algorithm E* suffices if E =28 and T =36hJM 1 Jlog(Jr\Jhl .

(a) A monomial m of F can be missing from g only because it has been removed from M1 by having occurred with frequency greater than E in the negative examples. This can only happen if the orac l e behaved erroneously at least ET times in T trials where the probability of each such occur­ rence is at mos t 8 = E/2 . By the b i nomi a l distribu­ tion (e . g . [3]) the probability of this happening is less than exp( - l/2 · ET) <exp(-4log <JM1Jhll < JM 1 Jh- l under the assumed bounds on T and o . Hence the probability of this happening to any m in F is at most h- 1 .

• (b) A monomial m such that D-(v) ~0 for some v such that m =>v can be included in g if there have been fewer than ET negative examples containing m. Now if some ro EM 1 is implied with frequency at l east 2E by Dthen the probability of having found at most ET negative examples in T trial s each wi th probability of success at least 2E (1 - o) [i. e . , allowing for the 8 error rate] can

be bounded above by exp( - (l/3) · 4oT(l-o ) · [(1- o)/(2- 28)] 2 ) <exp (- oT/9) . Hence the probabil­

• i t y that at least one such monomial with f r equency at least 2E has been wrongly included in g is at most 11l · exp( - oT/9) .;;h- 1 under the assumed bounds . Hence if onl y t hose monomials remain that have fre­ quency less than 2E then their total contribution to LD-(v) isatmost JM 1 J· (2hJM 1 JJ - l<;;h- l. o

5 . Naive Neural Modelling

The methodol ogy behind thi s study i s that of determining the largest classes of "concepts" , that can be learned in a feasible total number of compu­ tation steps. Since learning is exhibited by bio­ l ogical systems it is an interesting afterthought

to determine vThether the algorithms discovered hap­ pen to be well suited to implementation on a "brain­ like" model of computation, such as considered by Feldman [6] or Ackley et al. [1], for example .

In this section we observe that a partial im­ plementation of our algorithm on networks of linear threshold devices can be found that is noteworthy for its simplicity . In the propositional case it is able to learn DNF expressions if the distributions are such that the monomial sets are generable in a certain sense on these networks . While this class is still plausible and accommodates robustness exactly as in Section 4, it does require more res­ tricted distributions than before and does not allow

for the relations of Section 3.

The essential idea is that if the input nodes of the network are exposed to the vectors constitu­ ting the examples , then the monomials in the mono­ mial set M 1 will be learned in unsupervised fashion at various distinct nodes in the network . The final disjunction over these is learned in supervised mode at a speoified node . To accomplish the unsupervised stage symmetry in the network is broken by assuming randomness in the network (either of the connections or of the weights).

We consider the following distributed model of computation. An instance of a net is described by a triple (V,E,A) where V is a set of n nodes {1,2, ··· ,n} , ECV xv is a set of directed edges and A:E + [0 , 1] lab~ls each edge (i,j) with a numeri­ cal weight aij · Each node i has a state si that at any time has value 0 or 1 .

A set of nodes , say {l , ·.· , t } is regarded as constituting the input . When an example is presented to the net, for learning or recognition, the states sl· ····st are set to the Boolean values correspon­ ding to the truth values of the propositional predicates

Anode "fires" (i.e ., sj=l) interval if in the previous interval in a time

A node continues to fire as long as the above con­ dition holds .

The learning mechanism allowed is the following: When a new example is presented we wait for the states to stabilize and assume that they do. A wei ght aij can be changed only if node i or node j is firing . Its new value depends only on the current values of si , sj and on the values of aij and aji before the presentation of the current example. The new value of aij becomes operative only when a further example has been presented.

l'le consider two senses in which a net l earns a function F(p 1 , · ·· ,pt) as a consequence of a train­ ing session of examples. F has been learned in unsupervised mode if the weights have been so modi­ fied during the training session that some node now fires wheneve r (i . e . almost whenever) F(s 1 , ·.· , st) =1 . F has been l earned in supePvised

mode if the same has been achieved but in the course of the training session a distinguished node, say was controlled by an external omnipotent agent and made to fire if and only if F(s1 , ··· , st) =l was t rue of the training example (thus overriding possi­ b l y the threshold condition above} .

For implementing counters on the weights we use a n a rbitrary continuous strictly monotone function c [O ,l] -+ [0,1] such that for any cE(O,l) o r (c ) -+ l and o- r (c) -+ 0 as r -+=. [e . g. , o (x) = 2x - x2 , o-l(x) =l -~ would do] .

First , we notice that if F is a simple mono­ tone disjunction (e . g., p 1 v p 3 vp 7 ) or a simple monot one conjunc tion then it can be learned in super­ v i sed mode at any node j to which all the relevant i nputs are conne cted. The learning rule for dis­ j unctions involve s changing those a.. where (i,j) EE provided F =0 as follows~]

By duality l earning a conjunction is achieved by

In both case s a + l is the inverse of the E = 28 of Theorem 4 . 1. If each ail" is initialized to l/2 , say , then each aij wi l t e nd to 0 or las desire d a c cording to whe~ner its frequency in the corresponding examples is less than or greater than E .

To recognize disjunctions of conjunctions we wi ll show how c e rtain monomial sets 1-1 1 can be gen­ e r a t e d in unsupervised mode from examples. A dis­ j unction over any subset of· 1-1 1 can then be learned by t he above me thod at any node that is connected to a l l the nodes computing M 1 .

The bas ic idea is illustrated by the simple case o f wanting to learn the monomial p 1 p 2 .·· pk f r om a distribution D* of examples whe n the nodes l , 2 , ··· ,k, ··· ,d, are all connected to some node j >d. [Note that here D* will be a distribution tha t typically includes both positive and negative exampl e s of F and no-one informs node j as to which is the case .] To accomplish this we define o as above but scaled to the range [0, (k-l/2) -l], a nd choose it s o that l o (x) - xl is always suitably small compare d with k-1. If each aik is initial­ ize d to (k - 1/4) -1 then the following learning a l gorithm, for l ~i ~d , will achieve the task

p r ovided the distribution D* has favorable proper­ t i es such as the following :

If Y is the event that at least k of are l then

The idea is that for the majority of for Q, <k. These will cause sj to increase the values of a Q, · to tend (k-l/2)-l. For the remainlng values for the majority of inputs and hence tend to zero as desired. inputs SQ, = l fire and hence towards of Q, SQ, =0 aQ,j will

To make arbitrary monomials of length k (i.e ., 11 (k)) learnable in unsupervised mode, one approach is to make the network random so that for each set of k out of the n nodes, there will be at least one, and at most a few, nodes to which all k are connected . Connecting each node to a random set of about nl-1/k others achieves this. Then any monomial m E ~1 (k) can be learnt at some node, and , equally importantly, will be learnt at only a few, thus allowing the other nodes to learn differ­ ent monomials. In this way about n distinct mono­ mials from M(k) can be learnt. To make all this possible D* has to be so defined that at each node at most one monomial from M(k) has overriding influence in the sense of the previous paragraph .

To make the above concrete consider the case k = 2 and suppose that we want P l P2 to be learn­ able. Then D* has to be such that if we pick a set of In Pi ' s to include p 1 ,p 2 but to be othe r­ wise random, then with high likelihood the following holds: If v ED* is chosen randomly to have at least two of the chosen Pi true, then with prob­ ability greater than a half these will include pl and p 2 ·

To summarize we have shown that a restricted version of Algorithm E of Section 2 can be imple­ mented on a network of threshold e l ements . It will build up recognizers for a set M* of monomials that occur in examples provided the members of M* are suitably separated by D* in the manner indi­ cated above . The network can then learn arbitrary disjunctions over M* in supervised mode.

6. Simple Rules of Thumb May be Hard to Learn

There is evidence that certain significant extensions to the concept classes here or in [13] render them computationally intractable. One source of evidence is cryptography as described in the lat­ t er paper . Here we shall describe an NP-complete­ ness result that shows that extensions in a certain other direction are probabl y computationally intrac­ table also.

In the learnable classes considered a simple formula was assumed to account for a hundred percent of all positive example s of a concept. Suppose t hat the simple formula is now a single monomial that accounts for just fifty percent , and the rest is accounted for by a function whose complexity is unspecified. We shall show that in this situation it is NP- hard to discover e ither this monomial , or one that approximates it in the sense of accounting for (l/2 -h-1) of the distribution for arbitrarily large h.

Theorem 6.1. Given a function F expressed as a sum of monomials and distributions D+ and D- of pos itive and negative examples! it is NP-hard to determine whether a monomial m of the following kind exists, or to construct one if it does :

+ [The descriptions of D and D counted in the input size .) do not need to be

Proof. lve reduce the BALANCED COMPLETE BIPARTITE SUBGRAPH problem proved NP-complete by Garey and Johnson ((7], p. 196) to this problem. In the former problem we are given a bipartite graph G = (V=V 1 U V 2 ; E C::.V 1 x V 2 ) where IV 1 1 = IV 2 1 and we have to determine whether the r e are subsets u1 ::_v 1 and u2::_v 2 both of size lv 1 l/2 such that u 1 x u 2 ::_E.

Suppose we interpret the nodes v 1 as {p 1 , ··· ,pt} and define for each node q. E {q1 , ··· ,qt } =V2 a monomial mi such that m~ = n Pj with conjunction over all such that (j,il EE. Let D+(vi) =t-1 for each vi that is completely defined and has exactly those predicates true that occur in mi. Also let D-(v) > 0 when­ ever fewer than t/2 predicates are true.

Then the distribution ensures that any m satisfying the theorem must have at least t/2 predicates defined as true, and, also, must imply at least t/2 of the mi's. But this is exactly the condition that the graph G has a (t/2) x (t/2) complete bipartite subgraph.

The above shows that determining whether the desired m exists or not is NP-hard. Constructing it on the assumption that this good rule of thumb exists is therefore also NP-hard since the decision procedure reduces to this. o

Also if no such m exists then the value of [ D+(v) summed over all v~m is at most (l-t-l)/2 and the constant l/2 cannot be approached to within h-1 uniformly in a number of steps polynomial in h and t (unless NP-complete­ ness does not imply intractability).

Finally note that it is not known whether the size of the largest balanced complete bipartite subgraph can be approximated to arbitrarily good multiplicative constant factors in polynomial time. Hence it is possible that the above reduction estab­ lishes a s tronger result than claimed, namely that finding monomials accounting for (1/2 - E) of the distribution for sufficiently small constant E is also difficult.