tag:blogger.com,1999:blog-3722233.post112898083709841014..comments2020-03-29T11:49:19.890-04:00Comments on Computational Complexity: Favorite Theorems: Logical Characterization of NPLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-3722233.post-1131099955989400132005-11-04T05:25:00.000-05:002005-11-04T05:25:00.000-05:00"Fagin's theorem, as stated by Lance, might be inc..."Fagin's theorem, as stated by Lance, might be incorrect; this business is a bit picky about the structure (graphs, numbers, etc.) underlying the logic you're talking about."<BR/><BR/>With a bit or work, I believe Fagin's theorem could be reformulated in categorial terms, thus eliminating the problem you're pointing out.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1129255365718827512005-10-13T22:02:00.000-04:002005-10-13T22:02:00.000-04:00The alert reader might note that I left out a piec...The alert reader might note that I left out a piece of the story in my addendum to Lance's column. The class of NP properties that can be defined using only unary existentially quantified predicates is called "monadic NP". In the example I gave of 3-colorability, only unary existentially quantified predicates are used, and so 3-colorability is in monadic NP. Is every NP graph property in monadic NP? The answer is no: in a <A HREF="http://www.almaden.ibm.com/cs/people/fagin/zeit75a.pdf" REL="nofollow">1975 paper</A>, I showed that graph connectivity is not in monadic NP. In a <A HREF="http://www.almaden.ibm.com/cs/people/fagin/infcom95.pdf" REL="nofollow">1995 paper</A> with Stockmeyer and Vardi, we gave a simplified proof of this result. This result is especially intriguing, since it is easy to show that the complementary class (graph nonconnectivity) is in monadic NP. Hence, monadic NP is not closed under complement.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1129130728402786682005-10-12T11:25:00.000-04:002005-10-12T11:25:00.000-04:00Siva, thanks for your helpful comments. Lance has...Siva, thanks for your helpful comments. Lance has kindly posted my response to your question as an addendum.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1129014427451377282005-10-11T03:07:00.000-04:002005-10-11T03:07:00.000-04:00Apologies for the bad URL for the talk by Ron Fagi...Apologies for the bad URL for the talk by Ron Fagin. It is<BR/><A HREF="http://home.comcast.net/~dsivakumar/Ajtai-Fagin.ppt" REL="nofollow"> here</A>D. Sivakumarhttps://www.blogger.com/profile/04674739621423058308noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1128984460380479922005-10-10T18:47:00.000-04:002005-10-10T18:47:00.000-04:00Two comments:(1) As far as I know, it is an open q...Two comments:<BR/><BR/>(1) As far as I know, it is an open question whether every NP langauge has an existential second-order characterization with binary predicates only. See, for example, the <A HREF="http://home.comcast.com/~dsivakumar/Ajtai-Fagin.ppt" REL="nofollow"> talk given by Ron Fagin at a BATS meeting </A>.<BR/><BR/>In fact, it is conceivable AFAIK that every NP language has a second-order characterization with just one binary quantifier.<BR/><BR/>(2) To me, Fagin's theorem is perhaps the best argument we have for why NP is such an important class (aside from the empirical ones). NP is about searching for "solutions" to "problems", and as humans, we are quite limited in our ability to express what constitutes a "solution". The description "solutions that can be verified by a polynomial-time algorithm" isn't even close to what I believe to be capable of human expressibility. On the other hand, in virtually every real example, the "verifiability" of a purported solution can be distilled to a simple first-order sentence (e.g., if you want to produce a time-table for your university, you're looking for a relation (class, professor, room, timeslot) that satisfies natural constraints like "no professor can be present in two classrooms at same timeslot", "no room can hold two classes as the same time", etc.).<BR/><BR/>A nice counterexample to my claim above is factoring: I can't think of a simple first-order sentence that will tell us if N = p * q. With the logical structure most natural for the problem (integers, bits, etc.), it is likely that this is provably impossible (by reduction from PARITY). Yet factoring is in NP.<BR/><BR/>Btw, Fagin's theorem, as stated by Lance, might be incorrect; this business is a bit picky about the structure (graphs, numbers, etc.) underlying the logic you're talking about. (I am sure Ron will point out the subtleties very soon :-)D. Sivakumarhttps://www.blogger.com/profile/04674739621423058308noreply@blogger.com