tag:blogger.com,1999:blog-3722233.post111215038472244685..comments2023-09-30T21:44:03.907-05:00Comments on Computational Complexity: A Non-Standard PostLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-3722233.post-1117246951565351592005-05-27T21:22:00.000-05:002005-05-27T21:22:00.000-05:00Even if n is nonstandard, n-1 is always defined (u...Even if n is nonstandard, n-1 is always defined (unless n=0). Every countable nonstandard model of PA is order isomorphic to N + Q*Z, where Q*Z is the lexicographic<BR/>order of pairs (q,n) where q is rational and n is in Z. Hence there are infinite descending sequences if you're looking at the model from the "outside," but of course any nonempty subset that's *definable* in the language of arithmetic will have a least element.<BR/><BR/>By the way, if someone uses the term "theory of arithmetic" then they typically mean the set of all first-order sentences that are true in the standard model, and it doesn't really make sense to say that P=NP is independent of the theory of arithmetic in this sense. The intended term was probably "PA" or first-order Peano arithmetic.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1112199794716746862005-03-30T10:23:00.000-06:002005-03-30T10:23:00.000-06:00There is a paper in JACM by Attila Mate (vol. 37, ...There is a paper in <BR/>JACM by Attila Mate (vol. 37, no 1, 1990) followed by a paper in TCS (I don't remember the author). Together they give a necessary and sufficient for NP not to be equal to coNP in terms of nonstandard models of Peano arithmetics.<BR/><BR/>Gabriel IstrateAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1112192472528305612005-03-30T08:21:00.000-06:002005-03-30T08:21:00.000-06:00Actually, doesn't the original example break down?...Actually, doesn't the original example break down? It was my understanding that nonstandard numbers were like ordinals in that "n-1" is not necessarily well-defined, and that they can have no infinite decreasing subsequence? So any well-defined program following that outline would still have to terminate in a finite number of steps.<BR/><BR/>But, maybe I'm applying set theory inappropriately here, so I could be wrong...Anonymousnoreply@blogger.com