tag:blogger.com,1999:blog-3722233.post4862461993617611516..comments2024-11-03T21:27:06.200-06:00Comments on Computational Complexity: Are results about actual constants interesting?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-3722233.post-2787812727531939722009-02-09T21:16:00.000-06:002009-02-09T21:16:00.000-06:00I hadn't read Ryan Williams' "Applying Practice to...I 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 :)<BR/><BR/>If 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.Josh Burdickhttps://www.blogger.com/profile/12231348292069164630noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-52561973236552319642009-02-09T18:11:00.000-06:002009-02-09T18:11:00.000-06:00I agree entirely to the statements in the post. Ho...I 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.Unknownhttps://www.blogger.com/profile/07631055333881459954noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8160275108609382472009-02-09T15:42:00.000-06:002009-02-09T15:42:00.000-06:00I believe the fastest algorithms for finding a tri...I believe the fastest algorithms for finding a triangle in a graph use matrix multiplication. Could it be interesting in this context?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-17064000111839617242009-02-09T15:06:00.000-06:002009-02-09T15:06:00.000-06:00I don't care about multiplicative constants, let a...I don't care about multiplicative constants, let alone additive constants. :)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-12046648580615973262009-02-09T13:11:00.000-06:002009-02-09T13:11:00.000-06:00I am suspicious. This is not a small number of ga...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).Anonymousnoreply@blogger.com