tag:blogger.com,1999:blog-3722233.post2703513220387445599..comments2023-03-23T09:50:46.959-05:00Comments on Computational Complexity: What is an explicit Construction?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-3722233.post-45179073432586954102010-01-04T00:39:10.470-06:002010-01-04T00:39:10.470-06:00Calling such proofs 'probabilistic' has al...Calling such proofs 'probabilistic' has always bothered me because they're really counting arguments which make use of probability terminology to avoid some clunky multipliers which always cancel out in the end. They're all based on the idea that you count the amount of stuff that's removed, and in the end there's stuff left over, so they rely on the pigeon hole principle. One could say that any proof which doesn't rely on the pigeon hole principle is non-constructive, but using the pigeon hole principle across a linear number of elements doesn't have the same feel to it. What matters is the size of the set the principle is applied to.<br /><br />Since all constructive (in the logician sense) proofs implicitly give an algorithm for finding the solution, perhaps it's best to look at the asymptotic runtime of that algorithm. If it's polynomial then the construction is fairly direct, otherwise it's somewhat indirect.Bram Cohenhttps://www.blogger.com/profile/03952121644359153139noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-19076396286841527882009-12-19T03:18:49.259-06:002009-12-19T03:18:49.259-06:00Could someone please post a link to the Beigel pap...Could someone please post a link to the Beigel paper referenced in item 5.? thanks.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-64307345963282705622009-12-18T18:18:49.685-06:002009-12-18T18:18:49.685-06:00Bill, finally returning to the accustomed standard...Bill, finally returning to the accustomed standard of this blog. Please keep up this standard. <br /><br />Nice post.Good Postnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-55758590640808349022009-12-18T14:29:13.081-06:002009-12-18T14:29:13.081-06:00Good point, Bill! The whole lower bounds stuff in ...Good point, Bill! The whole lower bounds stuff in computational complexity is also "sick" about finding a "constructive" or "explicit" or "specific" hard to compute function. And nobody in fact cares about what these terms actually mean. Why? Since there is no need to care. We all know what we want: to understand why some functions are easy and the others <br />are hard. The same with "constructivity" in combinatorial proofs: if a good object exists, then it would be nice to try to see one constructed on 1-2 pages.. <br /><br />What we actually want is not to construct ("explicitly" or however) some artificial "complex" objects -- we want to known what makes them "complex".<br /><br />Actually, I am also a bit confused by this big rumor about Robin Moser's result. It is a cute and nice idea, no doubts. It made some previous results simpler. But what it really says about *why* SAT problem is so difficult? LLL already said that one of the reasons is a big overlap between clauses. What one (as a mathematician, not an applier) gets from the knowledge that LLL for SAT can (sometimes) be turned to an efficient randomized algorithm?<br /><br />Possible meanings of "constructive object":<br /><br />(a) Can be constructed in principle.<br /><br />(b) Can be constructed in reasonable (polynomial) time.<br /><br />(c) Can be described on 1-2 pages.<br /><br />I think Paul Erdos (as well as most of people working on lower bounds for boolean functions) would accept neither (a) nor (b) as "constructive. This is why we are happy to see things like 1 page construction of almost Ramsey graphs by Frankl and Wilson, etc.Stasyshttp://www.thi.informatik.uni-frankfurt.de/~jukna/noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-55346873086413275092009-12-18T13:10:34.452-06:002009-12-18T13:10:34.452-06:00Markk: standard way to say it is
There is a rand p...Markk: standard way to say it is<br />There is a rand poly time algorithm<br />that produces a correct coloring<br />with prob \ge 3/4. AND you can test if its correct. So if its not you can run it again. This is equivalent to prob \ge 1/2^n (or somethign like that).<br /><br />Anon 2: You are using the LOGICIANS definition of Constructive.<br />Perhaps combinatorists should use a diff term like Explicit.<br />The distinction between a<br />prob construction that just shows<br />something exists and an explicit<br />construction IS a real difference of interest.Bill Gasarchnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-31962431245925250312009-12-18T13:04:10.346-06:002009-12-18T13:04:10.346-06:00As a historical reminder, Claude Shannon's wor...As a historical reminder, Claude Shannon's work in 1948-9 on channel capacity was famously nonconstructive ... and Joseph Doob's AMS review of Shannon's work was (perhaps in consequence?) famously snarky ...<br /><br />"(Shannon's) discussion is suggestive throughout, rather than mathematical, and it is not always clear that the authorâ€™s mathematical intentions are honorable."<br /><br />@article{Author = {Shannon, C. E.}, Journal = {Bell System Tech. J.}, Pages = {379--423, 623--656}, Title = {A mathematical theory of communication},Volume = {27}, Year = {1948},annote={see Doob's review: MR0026286}}John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-19950955240525837292009-12-18T11:28:09.704-06:002009-12-18T11:28:09.704-06:00No, No, No! I don't care how much time it take...No, No, No! I don't care how much time it takes if I can demonstrates that something must exist by putting forth an algorithm to construct it then it, the proof is constructive. <br /><br />If I prove that something must exist then point out that because it exists an exhaustive search will find it, that is not constructive proof of it's existence, because a pre-requesite for the construction is the assumption that what you are looking for exists.<br /><br />So there is no need to further constrain the definition of constructive to avoid constructive proofs that are really non-constuctive proofs with an exhaustive search tacked onto the end, because it should be clear that the exhaustive search relies on the known existence of solution and thus is not constructing it. So all you do by adding the constraint is exclude some legitimately constructive proofs that just don't run in what you want to call "good time" from being categorized as constructive.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-58254355142630338912009-12-18T11:16:52.947-06:002009-12-18T11:16:52.947-06:00Somehow I'm hazy somewhat. So what would the d...Somehow I'm hazy somewhat. So what would the definition of probabilistic constructive look like? Would it be some kind of epsilon-delta thing such as: For any any epsilon > 0 One can with probability 1-epsilon find the solution in polynomial time? Is there a standard way to say these things?Markknoreply@blogger.com