He seems to have proven the following:
PROBLEM: Given a 6 vertex graph (via (6 choose 2) Boolean inputs) you want to determine if it has a triangle. If you want to build a circuit for this problem just using NAND gates, how many are required.
PARTIAL ANSWER: The problem requires at least 21 NAND gates. ((6 choose 3), plus one output gate; what you'd probably expect, in other words.)
He has asked me two questions that I toss out to the audience
- Is the result correct? (probably) Does it contradict anything known (I doubt that)? Does the proof seem correct? (I think so.)
- Is the result interesting? To me this is the more interesting question (or meta-question). Are results about actual concrete numbers interesting? My first answer is only if (1) they lead to more more general results, or (2) use interesting techniques. So the answer may be, using (1), I DON"T KNOW, and (2) may be subjective.
I am suspicious. This is not a small number of gates. A simple version of Razborov's clique argument yields an Omega(n^3/log^4 n) lower bound for monotone circuits on n-vertex graphs (e.g. see Jukna's Extremal Combinatorics book).
ReplyDeleteI don't care about multiplicative constants, let alone additive constants. :)
ReplyDeleteI believe the fastest algorithms for finding a triangle in a graph use matrix multiplication. Could it be interesting in this context?
ReplyDeleteI agree entirely to the statements in the post. However, as Ryan Williams notes in his recent paper "Applying Practice to Theory", the power of small examples cannot be underestimated. Indeed, while the constant 21 itself is not interesting, it would be good to know that for small values of n an optimal circuit for the considered function is the straightforward one.
ReplyDeleteI hadn't read Ryan Williams' "Applying Practice to Theory", but yes, he seems to be thinking along really similar lines (not exactly the same problem, but using NOR gates is basically the same idea :)
ReplyDeleteIf the sKizzo solver which they used uses some sort of variable ordering (as BDD solvers do), then, if it gets anywhere on this problem, it might be interesting to see which variable orderings give the shortest/fastest proofs.