tag:blogger.com,1999:blog-3722233.post114727960256024727..comments2020-05-27T23:17:32.309-04:00Comments on Computational Complexity: The Importance of Natural ProofsLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-3722233.post-1147341855332013362006-05-11T06:04:00.000-04:002006-05-11T06:04:00.000-04:00My apologies if my observations appear off-post.I ...My apologies if my observations appear off-post.<BR/><BR/>I was merely commenting on a foundational aspect of the significance, and a possible cause of the perceived constraints on, Razborov-Rudich's 'imprecise' concept of 'natural proofs', to which the author's draw attention.<BR/><BR/>The author's argument seemed to be that if natural proofs were capable of precise, algorithmic, definition, they would "break pseudorandom generators and in particular imply that the discrete logarithm is not hard".<BR/><BR/>My intention was to suggest the possibility that natural proofs may be precisely definable instantiationally.<BR/><BR/>BhupAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1147338435674738532006-05-11T05:07:00.000-04:002006-05-11T05:07:00.000-04:00Bhup, the post and the Razborov-Rudich paper deal ...Bhup, <BR/>the post and the Razborov-Rudich paper deal with the non-uniform setting of proving circuit lowerbounds, and in particular, seperating NP from P/poly;<BR/>How does your post relate to circuit lowerbounds?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1147333831060477382006-05-11T03:50:00.000-04:002006-05-11T03:50:00.000-04:00====================In their paper, Razbarov and R...====================<BR/>In their paper, Razbarov and Rudich simply give evidence of a general limitation on the ability of highly combinatorial techniques, and their recursion-theoretic predecessors, to resolve P =/= NP and other hard problems.<BR/><BR/>This should not be very surprising, since all such techniques are, essentially, dependent on algorithmic methods of determining satisfiability.<BR/><BR/>Note that, Tarski's Theorem is that the set of true arithmetical propositions is not arithmetical.<BR/><BR/>Similarly, P=/= NP, is the assertion that the set of true arithmetical propositions is not algorithmic.<BR/><BR/>In other words, if we can define an arithmetical tautology that is not algorithmically decidable, then P=/=NP.<BR/><BR/>The question, therefore, is whether there is a way of defining an arithmetical relation f that is instantiationally provable as true for any given set of values to the variables of f, but f is not algorithmically provable as true for any given set of values to the variables of f.<BR/><BR/>The reason the PvNP problem 'seems' hard is that the distinction between instantiational provability and algorithmic provability, and its consequences, remains implicit so far.<BR/><BR/>To place the distinction in perspective, note that the PvNP issue can be expressed conveniently in terms of Goedel's interpretively true, but formally unprovable, arithmetic proposition, say [(Ax)R(x)].<BR/><BR/>Is Goedel's meta-mathematically proven, arithmetical, tautology, R(x), algorithmically provable?<BR/><BR/>If not, then P=/=NP.<BR/><BR/>However, if it is algorithmically provable, then it follows that there is some non-standard domain of values that satisfy the Peano Axioms, PA, over which R(x) is not tautologically true, even though it remains tautologically true over the sub-set of natural numbers in the domain of every interpretation.<BR/><BR/>The question arises: Does any such domain exist?<BR/><BR/>Now, if it exists, then it follows that each of the PA-unprovable formulas, [(Ax)R(x) and [~(Ax)R(x)], can be added as axioms to PA without affecting the recursive definability of PA, and without inviting inconsistency.<BR/><BR/>Now, it can be argued that the theorems of any recursively definable arithmetic - such as PA, PA+[(Ax)R(x)], PA+[~(Ax)R(x)] - are algorithmically provable as true over every domain of an interpretation (since the axioms of PA are algorithmically provable in any interpretation, and the rules of inference preserve algorithmic provability).<BR/><BR/>However, It would then follow that Goedel's arithmetical relation, R(x), is, both, algorithmically provable as true, and not algorithmically provable as true, over the natural numbers.<BR/><BR/>It follows that no non-standard domain, such as the above, can be defined consistently, and so P=/=NP.<BR/><BR/>BhupAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1147289677280923072006-05-10T15:34:00.000-04:002006-05-10T15:34:00.000-04:00One possible critique -- it's true that a "proof" ...One possible critique -- it's true that a "proof" that C is hard is superfluous. However, the vast majority of hard predicates, including all known NP-complete (or even complete-on-average) problems, still have large easy subsets, which is all that is required for natural proofs. Thus, your predicate might be hard to compute in general, but if it even has a sub-polynomial fraction of easy instances, that can still be enough for natural proof limitations to kick in. I think it is fair to say that right now, we are a very long way from building any <I>useful</I> predicates that have no non-negligible easy subsets ("useful" meaning something beyond being useful <I>because</I> of its hardness, as in cryptographic primitives or diagonalization).<BR/><BR/>I think this is a minority opinion (or at least one that Razbarov-Rudich disagree with), but because of the preceding I think attacking the largeness constraint is more promising right now. There is a long way to go in either case, but I think we are closer to building highly specialized/rare function properties than we are to finding useful predicates with no easy subsets.Anonymousnoreply@blogger.com