outline for a NP vs P/poly proof based on monotone circuits, hypergraphs, factoring, and slice functions

11 Replies

p_vs_np_rewardhi all.. quite a bit has happened since last blogged…

  • got my 1st 7 day timeout from a hardnose neophytish moderator on my favorite online forum (guess which one!) for a minor-at-best, nonexistent-at-worst infraction. its a long story and maybe also even a badge of honor =)
  • via same forum, within the last few days started an amazing/involved chat session with one of my all-time favorite complexity theory authors “SJ”
  • SJ tipped me off on a remarkable new proof of P\neqNP by fukuyama. am following his blog already, see link on right side of pg. signed up on nielsen’s polymath wiki merely to post this remarkable find/paper. *defn* more on that later. but on early glance it looks *way* more solid/promising on the deolalikar proof [1,2,3,12] which caused a lot of commotion & even got media attn. and its using *monotone circuits* which has been my own line of attack for many years (maybe closing in on a decade or so now). cant wait for the online reaction. or will a tree fall in the forest that nobody hears? =(
  • got nielsen’s outstanding/visionary book [and I never use that term lightly, wink] on collaborative science [11] in the mail from amazon too. looking fwd to reading that.
  • a respectable 250 hits on the blog so far with very little publicity. about 4 spam comments. no real humans showing up so far in the comments yet. big ouch there! guess this blogging thing is actually something like a religion because one has to have _faith_ that somebody’s really reading it & will eventually write, wink

anyway, onward! heres more insider bkg info for you. started this blog because I had some nice new ideas about a P\neqNP proof outline. this entry contains those ideas!

debated carefully on how to title this and introduce it. could call it a “proof sketch” but many real papers use that phrase to refer to real proofs that exist in their heads or elsewhere but they dont want to write all the details. will fully admit/concede *the following does not have all the details fleshed out*. its a high level idea based on my best knowledge/ability & could possibly be worked into a proof someday.

to me proofs are very much like software and have a strong correspondence/resemblance. believe this connection will be highly stengthened in the years to come in the theory. software has an *architecture* and architecture has *blueprints*. this is certainly not a blueprint, but it is maybe something like a blueprint sketched on a napkin. or at least a sketch written in blue pen. whatever! note that this will be fairly technical in some places.

* * *

heres the overall perspective. P vs NP can be studied from circuit theory in the NP vs P/poly problem. now via theory one can use any NP complete problem, but my favorite is SAT, because SAT is itself a fundamental circuit theory problem. for years, wondered if there was some way to “diagonalize” circuits in the proof, and get some kind of proof by contradiction that if there are small circuits then eg some classes in the time hierarchy theorem would be computed faster than the speed limit allows. the diagonalization thought am sure has occurred to many other researchers. never did figure that out exactly so far…

so of course imagine that there are circuits for solving SAT. how big are they? it is easy to exhibit circuits that grow exponentially in size wrt input sizes. but so far virtually impossible to prove lower bounds on these circuits.

anyway, SAT is also nice because one can easily encode other NP complete problems in it & even those not known to be NP complete, but conjectured to be hard, eg factoring. an interesting exercise there which I did in my early 20s.

and one of the most basic NP complete problems to encode in SAT (aka CNF) is the monotone clique problem. consider a graph of n vertices with c_1=\binom{n}{2} edges, each denoted by a binary variable say x_i. now exhibit the monotone circuit for detecting cliques of size exactly m vertices. each clique has c_2=\binom{m}{2} edges. the SAT formula has \binom{n}{m} clauses. each clause has c_2 variables. and there is a set of these circuits, one for each graph size, call them C_n.

so P\stackrel{?}{=}NP is a consequence of the stronger NP\nsubseteqP/poly and asking whether C_n can be expressed in size O(p(n)) where p(n) is polynomial.

but notice the symmetry of C_n. this is clearly a highly symmetric object. in fact a natural question in SAT studies is to look at the “clause graph” connectivity which is the graph where there is one vertex per SAT clause, and the vertices are connected if the clauses have any common variable. this is a deep topic and an entire Phd thesis could easily be written on the subject, and one has! [4]

and the clause graph of C_n is … an old familiar friend … a regular graph! exercise for the reader: how many edges does each vertex have? [6]

and heres another critical factoid: C_n is *very similar* to a *slice function* for which it has been proven that if the monotone circuit complexity is exponential, then the *nonmonotone* circuit complexity is also. (more on this later/below).

* * *

now heres the twist that is not really seen in many complexity theory papers.

mono-SAT-hypergraph lemma: every *monotone* SAT formula is also a *hypergraph*. there is a simple 1-1 correspondence between clauses and edges, and variables and vertices.

this point of view is not found in many places. there may be some papers that refer to sunflowers in terms of hypergraphs, and there are some deep complexity papers (eg Razborov style proofs) that refer to sunflowers, but there are not many complexity papers that refer to hypergraphs.

this may not seem like a big deal but its importance should not be understimated. hypergraphs are an area of recent increasing study and that theory can be leveraged. moreover, the vast area of graph theory is slowly being reworked into new hypergraph analog theorems of important graph theorems. in other words, the hypergraph perspective of circuits may lead to important bridge theorems between two large but at times separately developed “continents” of theory.

anyway looking at C_n in terms of hypergraphs and circuits simultaneously leads to the following picture. think first of C_n as a circuit. the question of the complexity of C_n comes down to asking if it can be expressed as smaller subcircuits with either a single AND or OR gate at the top (it can be assumed without much loss of generality that gates only have two inputs).

but believe it or not, and this is a fact rarely pointed out in complexity theory, in EE, electrical engineering, it is a key area of VLSI logic study to find smaller subcircuits for a given circuit. here it is referred to as a *factoring* algorithm. ie a larger circuit is *factored* into two smaller subcircuits. this problem has been studied in EE for decades, and it is known and understood to be very difficult with some CS reference to complexity theory.

in EE there are also software implementations that succeed on some smallish size circuits of say a few hundred gates, and these implementations are also almost always *approximate* algorithms. ie they find smaller circuits via factoring, but are not guaranteed to find the smallest such factors. for a near survey ref eg see [5].

so a way to look at this is that one would like to have an algorithm that could *factor* the C_n if there are any factors at all. this can also be seen as a general *decomposition* algorithm. the algorithm needs to be *exact* ie it will always succeed if such factors exist. so the EE research is not directly relevant, it is more of a fruitful analogy/perspective. in EE the researchers gave up on exact algorithms almost from the beginning. however one can study the EE circuit factoring algorithms for some insights. now here is the punchline:

circuit factoring lemma: the circuit C_n can be built out of smaller DAG circuits *iff* it can be factored!

* * *

now switch the pov to hypergraphs. if a SAT/CNF is also a hypergraph, what does it mean to factor this hypergraph? the SAT/CNF can be factored into subcircuits, but what does it mean to “factor” a SAT/CNF hypergraph? there is indeed some recent research into hypergraph factoring but unfortunately it is apparently not directly applicable to this problem. there is a new sense of factoring hypergraphs embedded in the following theorem.

hypergraph composition from circuit DAGs theorem: consider a monotone circuit represented as a DAG. that circuit be “fully multiplied out” to obtain a CNF or DNF at the top level. its sometimes called the “standard simplification rule” in EE textbooks. namely the distributive law of multiplication recursively, iteratively, inductively applied to the DAG in the form of a POSE or SOPE (product of sums expression or sum of products expression) .

if the inputs to the circuit are given as CNFs and DNFs, these can be modelled as “sub-” hypergraphs. and then the final expansion after all the multiplications can be seen as a hypergraph. the process of this monotone expansion involves two parts recursively applied:

  1. if one is taking the OR of two sub-hypergraphs H_1,H_2, the OR hypergraph H is just the new hypergraph with the set of all edges of the two hypergraphs combined.
  2. if one is taking the AND of two sub-hypergraphs H_1,H_2, the AND hypergraph H is just the new hypergraph constructed using a “cartesian bitwise join operator”. [7]

this “cartesian bitwise join operator” is an apparently somewhat newly studied operator in complexity theory and also mathematics, cannot find much reference to it after several queries! [8,9] it may look unfamiliar, but… it has actually been hanging around and hiding in plain sight!

approximation reformulation proposition: the cartesian bitwise join operator actually shows up in all circuit approximation proofs eg Razborov 1985, Alon-Boppana, etc. ie it is actually intrinsic to the process of converting SOPEs to POSE and vice versa in approximation proofs.

what the hypergraph composition says is that if a circuit such as C_n can be “decomposed” into a DAG it must be a combination of operations (1) and (2) above combined with what is known in SAT as “subsumption” of clauses. but it also appears to me:

subsumption conjecture: the subsumption operation in the above decomposition is not important to the circuits involved NP vs P/Poly problem being studied in particular C_n for the monotone clique problem.

so what this says is that only operations (1) and (2) are relevant and subsumption that occurs in converting the DAG to the “normalized” C_n form is not an important consideration and can be disregarded somehow (or as having “negligible” effect).

* * *

now, here is another key conjecture that significantly simplifies the problem:

big-factor conjecture: operation (1) may occur but it cannot lead to that many clauses in C_n. there must still be some “large” factors in C_n that are built up using operation (2). moreover since factors can be combined, it can be reduced to only two large factors that bitwise-joined together equal “many” clauses of C_n.

so this says that operation (2) is the key operation to understand factoring C_n. it says that C_n must have some large factors under the cartesian bitwise join operator. in other words its saying there must exist some particular shaped “large” structures in the hypergraph. but this is vaguely reminiscent of many theorems that prove some particular “large” structures dont exist in graphs (eg Ramsey graphs that have no “large” cliques).

and here is also where there is some empirical evidence that comes into play. it is easy to write a program that creates two random hypergraphs H_1 and H_2 and multiplies them, and look at the results. this is obvious to state in retrospect, but unless H_1 and H_2 have the same number of vertices in each edge, and they are *disjoint* (in the vertex sets in the hypergraphs), then the results will have many edges with an irregular number of vertices, ie never a single constant number of vertices in the edges. but that is a bit strange, because obviously C_n has a constant number of vertices c_2 in every single edge!

in fact the cartesian bitwise join of two hypergraphs where the hypergraphs have disjoint vertices appears to have a strong resemblance to what are known as *multilinear formulas* [10] for which apparently there are some good lower bound results known (exponential).

so after all that a remaining wrinkle is the resemblance of C_n to a slice function which is not totally apparent. this is covered by a lemma:

“topless slice” lemma: a slice is composed of a “section” ORed with a “top” (a threshhold function) and therefore one can convert C_n to a slice function, and a slice function to C_n without much increase in gates either way.

a slice can be written in the form (X \wedge Y) \vee Z where Z is a threshhold function for hamming weight of 1 more than the slice “section”. a “section” X \wedge Y is defined as a set of prime implicants (minterms) of exactly the same hamming weight.

note that in the definition of slices, it is not guaranteed that it has a top level \vee-gate instead of an \wedge-gate. the case for the \wedge-gate is slightly harder to prove, but think it can be shown without too much trouble under the assumption that P=NP (exercise for reader). and also there may be some dual properties to exploit here, although note its proven that converting \vee formulas to \wedge formulas can lead to an exponential blowup in worst case (ie proven lower bounds).

ok! that is the overall outline. obviously it all has to be fleshed out further. however, at this point it all seems intuitively plausible, eh? one of the important ways that monotone function theory is very valuable is the following. suppose that one is working with nonmonotone SAT formulas. it is a very difficult problem to determine if two SAT formulas are equivalent which apparently involves enumerating all their prime implicants/minterms, which can apparently also lead to exponential blowup. for details, see EE circuit minimization textbooks eg the Quine McCluskey method. but for monotone formulas, there is a unique representation. that is a valuable property that highly favors monotone circuits and is utilized directly in the above outline.

so, hey, cyberspace… any reaction(s)? wheres the big fat hole in all that? =)

11 thoughts on “outline for a NP vs P/poly proof based on monotone circuits, hypergraphs, factoring, and slice functions”

  1. leegao

    Hey there, I’m not TCS but I just want to give you a shout out; keep up the awesome work and the refreshing enthusiasm. I hope this comment finds you well 🙂

    Reply ↓
  2. Luke

    You probably should describe how this avoids the natural proof barrier. That’s the first thing people will look for before taking this seriously.

    Reply ↓
  3. Philip White

    Nice to see I’m not the only one who is interested in actual discussions of proofs attempts for P != NP. Could you describe a “brief summary” of your approach? I don’t have the training to follow all of your logic above. Like you, I claim to have found an approach that proves P != NP. Good luck getting anyone who is considered an “expert” to take a look at it or check it….

    Reply ↓
  5. fredgillet

    [the question of the complexity of C_n comes down to asking if it can be expressed as smaller subcircuits with either a single AND or OR gate at the top (it can be assumed without much loss of generality that gates only have two inputs).

    but believe it or not, and this is a fact rarely pointed out in complexity theory, in EE, electrical engineering, it is a key area of VLSI logic study to find smaller subcircuits for a given circuit. here it is referred to as a *factoring* algorithm. ie a larger circuit is *factored* into two smaller subcircuits. this problem has been studied in EE for decades, and it is known and understood to be very difficult with some CS reference to complexity theory.]

    Interesting! That’s exactly what I’ve done.

    Reply ↓

  7. Pingback: algebraic circuit complexity, Valiants VP=?VNP, recent advances/ breakthroughs | Turing Machine

  8. Pingback: leading authorities weigh in on P vs NP proofs | Turing Machine

  9. gentzen

    Except for the “topless slice” lemma, everything you write only applies to monotone circuits. So all your information about hypergraphs, subsumption conjecture and cartesian bitwise join operator is only relevant, if it is needed to show that the monotone circuit size of the slice functions of C_n doesn’t increase much over the monotone circuit size of C_n.

    However, you don’t explain the slice functions of C_n in a clear way, let alone explain why the circuit size won’t change much. This chapter from “Models of Computation” by J. Savage contains at least a clear definition of the slice functions. It also contains the proofs showing that your general strategy would succeed, if only you could show that the monotone circuit size of the slice functions of C_n won’t change much.

    Reply ↓

  10. Pingback: norbert blum P vs NP attack goes CYBER-SCIENCE-VIRAL! | Turing Machine

  11. Pingback: How is a hypergraph different from a bipartite graph?

Leave a comment