# potential of the approximation method[精选推荐pdf]

Potential of the Approximation Kazuyuki AmanoAkira Maruoka Graduate School of Ination Sciences, Tohoku University Aoba-ku Sendai 980-77, JAPANama,maruokaecei.tohoku.ac.jpNovember 20, 1996AbstractDeveloping some techniques for the approximation , we establish precise versions of the following statements concerning lower bounds for circuits that detect cliques of sizein a graph withvertices For 54, a monotone circuit computing CLIQUE contains at least1218min124gates If a non-monotone circuit computes CLIQUE using a “small” amountofnegation, thenthe circuitcontainsanexponential number of gates. The er is proved very simply using so called bottleneck counting argument within the frameworkof approximation, whereas the latter is verified introduc- ing a notion of restricting negation and generalizing thesunflower contraction.1. IntroductionSince Razborov, based on the approximation , suc- ceededto obtain a superpolynomial lowerbound on the size of monotone circuits computing the clique function, much effort has been devoted to explore the and derive good lower bounds[K, NM, R1, R2, RR]. Employing the approximation, AlonandBoppana[AB]obtainedan exponential lower bound for monotone circuits computing the clique function. Using seemingly different argument, called bottleneck counting, Haken[H] derived an exponen- tial lower bound for monotone circuits computing a variant of the clique function. Furthermore, it was shown that the extended approximation , in principle, can provide tight lower bounds for non-monotone circuits[R2]. In spite of these progress in proving lower bounds, the question of how to apply the to obtain good lower bounds has remained largely unknown. In this paper,we explore further the in two ways.First, we use the bottleneck counting ar-gument within the framework of approximation so as to obtain exponential lower bounds for monotone cir- cuits computing the clique function as well as someother function defined in terms of polynomials.De- noting the clique function detecting cliques of sizein a graph withvertices by CLIQUE, our lower bound for monotone circuits computing CLIQUEis given by1218min124for 54. The best lower bound obtained so far for the clique function is18432log12for 314log23due to Alon and Boppana[AB]. So as for the largest monotone lower bound for the clique func- tion, our bound is exp13for23, whereas theone dueto Alonand Boppanais explog13 for14log23.Asan another example ofthe first line, we obtaina lower bound for monotone circuits computing the polynomial problem and obtained the same lower bounds due to Alon and Boppana which is to this date the best lower bound for the monotone circuit complexity of a problem in NP.To derive these lower bounds, we define approximators,instead of relying on the sunflower contraction, in terms of DNF and CNF ulas such that the size or the length of terms and clauses in the ulas is limited appropriately. In this way, the proofs to obtain these bounds are greatlysimplified using only elementary combinatorics.Second, we explore the possibility of introducing ap- proximate operations for non-monotone cases so as to ob- tain lower bounds for non-monotone circuits. To do so, we introduce a notion of restricting negation used in a circuit. For circuitwith variables1...¯1... ¯, let its monotone analogue, denoted, be the monotone cir- cuit obtained by replacing each negated variable ¯in with a new variable. Then the maximum number of variables1...appearing in a minterm computed by the monotone analoguecan be viewed as showing an amount of negation used in. So setting the maximum1number to an integer between 0 and, we can get a variety of restrictions ranging from the restriction to monotone to no restriction.Based on the notion of restricting nega- tion, we verify that if a non-monotone circuitcomputes CLIQUEand the maximum number of the new variables appearing in a minterm computed by the mono- tone analogueis at most2, the the size of circuitis given by2, whereandare any constants such that 006 and 005. One might think of the result as showing the extent to which the proof along the line given by Alon et al.[AB] can be generalized to apply for non-monotone cases.2. PreliminariesABoolean circuit is a directed acyclic graph. The nodes of indegree0 are called nodes, and are labeled withor itsnegation ¯. The nodesof indegree2 arecalled gatesand are labeled with the Boolean functions AND and OR. AND and OR gates are also calledandgates, respectively. A circuit represents a Boolean function computed at a node in the circuit designated as the output node. In particular, a Boolean circuit without nodes labeled with negated variables is called monotone.The size of a circuit is the number of gates in the circuit.For argument’s sake, in Section 3 a monotone circuit is further assumed to satisfy the following conditions Any of angate is connected to either an output ofgate or an node, and any of angate is connected to either an output ofgate or an node; The output gate is angate. Any monotone circuit can be easily converted to the one satisfying these conditions by replacing, if necessarily, a line connecting gates by a dummy gatethat can be thought of as angate or angate, appropriately with their two s being connected to an output of the same gate, and hence by at most doubling the size of the circuit. The circuit complexitymonotone circuit complexity of a functionis the size of the smallest circuitmonotone circuit computing.3. Lower bounds for monotone circuit com- plexity based on size-based approximatorsIn this section, we derive lower bounds for the cliqueproblem and also those for a problem defined in terms of polynomials. The clique function, denoted CLIQUE, of12 variables1isdefined to take value 1 if and only if the undirected graph onvertices represented in the obvious way by the contains a clique of size. The graphs will be identified with the assignments to the variables specifying the graphs.Theorem 1If 54, then any monotonecircuit that computes the function CLIQUEcontains at least1218min124gates. In particular, the monotone circuit complexity of CLIQUE23is exp13.Wenow proceed to proving Theorem 1 in the frameworkof approximation. We define good and bad graphs which areused astest sto comparethe circuit’sbehavior with the behavior of the clique function. A graph is called good if it consists of a clique on some set ofvertices, and no other edges. A graph is called bad if there exists a partition of the vertices intomod1sets of size1 and1mod1sets of size1such that any two vertices chosen from different sets have an edge between them, and no other edges exist. Note that the function CLIQUEoutputs value 1 on every good graph and outputs 0 on every bad graph.Fact 1There aregood graphs and1111bad graphs, wheremod1.Letbe a term or a clause. The endpoint set ofis a set of all endpoints of the edges corresponding to variables in. The size ofis the cardinality of the endpoint set of.We are ready to define an approximator circuit to ap- proximate a monotone circuit. An approximator circuit is just the same as a Boolean circuit except thatandgates are replaced withandgates, respectively, which willbe defined below. Approximators computed at the nodes inan approximator circuit are defined in bottom-up fashion, starting from the nodes and then working up. The approximate gates, denotedgate andgate, are defined to behave as follows. The approximator corresponding to variableis defined to beitself. The functions of angate and angate are defined as follows. Integers andin the definition are chosen later. Let 1and 2be two approximators, represented by monotone DNF ulas, feeding into angate. The approximate OR of these approximators is the monotone CNF ula obtained by transing the monotone DNF ula 1 2into the monotone CNF ula and then taking away all the clauses whose sizes exceed. Let1and2be two approximators, represented by monotone CNF ulas, feeding into angate.2The approximate AND of these approximators is the monotone DNF ula obtained by transing the monotone CNF ula12into the monotone DNFulaandthen takingawayallthetermswhose sizes exceed.Since we assumed that no output of anresp. gate is connected to anresp. gate, an approximator computedatangateisgivenbyamonotoneCNFula, and an approximator computed at angate is given by a monotone DNF ula, where both ulas satisfy the size requirements. For Boolean functionsand, let us denoteif and only ifholds for any vector. Note that by the definition1212 holdsfor anymonotone DNFulas1and2. Similarly,1212holdsforany monotoneCNFulas1and2. Letbe a monotone circuit computing CLIQUE, and letcalled the approximator circuit corresponding to denote the circuit obtained by replacing all of theandgates inbyandgates, respectively. Since the computation inproceeds from bottom to top, it is easy to seethat, foranygood graphthatmakesapproximator circuitoutput 0, there exists angate that outputs 0 for thegood graph because of taking the terms away in defining its output approximator. So, angate feeded the same approximators as those to thegate outputs 1. Similarly, foranybadgraphthatmakesapproximatorcircuitoutputs 1, there exists angate that outputs 1 for the bad graphbecause of taking the clauses away in defining its output approximator. Theproof ofTheorem1 proceedsas follows First, showthat either of the number of good graphs that are classified wrongly by the approximator circuit or the number of badgraphsclassifiedwronglyislargeLemma1. Second,show that the number of bad graphs for which an approximate gatei.e.,gate behaves differently from angate is small Lemma 2 and similarly the number of good graphs for which an approximategate i.e.,gate behaves differently from agate is small Lemma 3. Finally, calculate the numbers obtained by dividing thenumbers of bad and good graphs classified wrongly by an approximator circuit by the numbers of graphs for which the corresponding approximate gates behaves differently, respectively, and show that the larger of the two numbers calculatedbecomes large, completing the proof of Theorem 1. The parametersandare put as12and4.Lemma 1An approximator circuit either outputs iden- tically 0 or outputs 1 on at least one half of the bad graphs.ProofLetbetheapproximatorfunctionthatanapprox-imatorcircuit computes. Becauseof the assumptionthat the output gate of an approximator circuit isgate,can be representedbyamonotoneDNFulaconsistingofterms ofsizeatmost. Ifisidentically0thenthefirstconclusion holds. If not, then there is a termwhose size is less than or equaltosuchthatholds. Inwhatfollows, badgraphs are represented as one to one mappings from vertex set1...to11,...,11, ...,1,...,111...1121...11.Such a mappingspecifies a bad graph in the obvious way Two vertices in the graph have an edge between them if and only if themapping assigns to the vertices a pair with different first components. Note that there exist many mappings corre- sponding to one bad graph. It is easy to see that the ratio of mappings that satisfy the condition that there is a variable inthetermsuchthattwo verticesincidenttoareassigneda pair with the same first component, i.e., the termoutputs0 on bad graphs specified by such mappings, is at most121. Recalling12, above quantity is bounded from above by 12. Therefore, the ratio of bad graphs such thatoutputs 1 on them is at least 12.Lemma 2Suppose that angate and angate are given as the same monotone DNF ulas such that the size of terms in the ulas is equal to or less than. Then the number of bad graphs for which theandgates produce different outputs thegate produces 0, whereas thegate produces 1 is at most21111111ProofSuppose that angate and angate are given as the same monotone DNF ulas, denoted1 and 2, such that the size of any term in the ulas is equal to or smaller than. Let 1 2and 1 2be denoted byand, respectively. Let1...be the complete list of terms in. Then eachcontains at most12 variables.We shall count the number of bad graphssuch that both0 and1 hold. As in the proof of Lemma 1, bad graphs are represented as mappings described there. Instead of counting bad graphs directly, we count mappings corresponding to bad graphs. The number in question is bounded from above by the number of the mapping corresponding to bad graphssuch that0 and1 divided by the number of mappings corresponding to one bad graph. The latter number is independent of a bad graph chosen. Since thelatter is given by the denominator of 1, it suffices to estimate the er. The er is the number of mappings corresponding to bad graphsthat do not satisfy any of31...but satisfy all clauses in. We count how manywaysone couldchoose variables eachfrom terms1upto andassign pairs of integers to the endpoints associated with thevariables chosen so that the corresponding bad graphs satisfy0 and1. Suppose that we proceed to termand hence some of theendpointsassociatedwithvariablesfromterms1to1 are already assigned distinct pairs of integers. This partial assignment assigns 0 and 1 to some of variables in the waymentioned above. We first consider the extreme cases. If there exists a variable in termalready assigned 0 by the partial assignment, we skip to the next term1. The other extreme case occurs when all the variables in termare assigned 1 so far. In this case termwill never take value 0, hence we don’t need to consider the case. If neither of these extreme cases happens, choose a variable from termsuch that at least one of the vertices associatedwiththevariableisnotassignedapairofintegers. There are two cases to consider If exactly one of the vertices is assigned so far, then assign to the remainingvertex a pair whose first component is identical to thefirst component of the pair of integers assigned to the other vertex so that the variable associated with the two vertices is assigned 0.In this case, there are at most111ways of assigning pairs of integers