tag:blogger.com,1999:blog-3722233.post8993610381615285299..comments2022-12-01T12:05:03.445-06:00Comments on Computational Complexity: When to declare a problem is hard?/Constructive versions of Dilworth's theoremLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-3722233.post-54028353020687614842009-01-31T09:18:00.000-06:002009-01-31T09:18:00.000-06:00OFF TOPIC: I seem to recall a letter from Kurt God...OFF TOPIC: I seem to recall a letter from Kurt Godel (to John von Neumann?) saying something to the effect that Godel was doubtful that the intuitive concept of computation could ever be satisfactorily formalized. If this isn't a false memory, I would appreciate a pointer to the exact quote.<BR/><BR/>Kirk PruhsAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-14093730049729765222009-01-31T02:57:00.000-06:002009-01-31T02:57:00.000-06:00NL vs co-NL is a beautiful result but by that poin...NL vs co-NL is a beautiful result but by that point in time it was already known that the logspace hierarchy collapsed to the second level in a result due to Lange, Kirsig, and Jenner. Now that result was a surprise.<BR/><BR/>Lots of people have worked on much problems that would be implied by a separation of NL and NP and are much easier. Uniform circuit lower bounds, time-space tradeoff lower bounds, etc, We're stuck at uniform-AC^0[6] vs NP - the best we have is a separation of this from #P. A large effort in complexity has gone into this problem.<BR/><BR/>On the flip side there has been much less work on P vs PSPACE.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-25724956306988211852009-01-30T17:51:00.000-06:002009-01-30T17:51:00.000-06:00The funny thing is, once the idea that a problem i...The funny thing is, once the idea that a problem is hard is perpetuated sufficiently widely, it attracts fewer and fewer people to work on it, and over time, builds up a reputation of being hard even if not many people have looked at it closely enough.<BR/>By association, "similar" problems also become labeled as hard - I am not sure many people have thought about P vs PSPACE or NL vs NP deeply enough. Thus when something like NL = co-NL is proved, it comes as a huge surprise.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-39770165438440835942009-01-30T16:55:00.000-06:002009-01-30T16:55:00.000-06:00Anon2- There are many different ways to fomulate t...Anon2- There are many different ways to fomulate the question<BR/>``is their a constructive proof of this theorem?''. I presented<BR/>one approach- the computability<BR/>approach. <BR/><BR/>Your question could be made<BR/>rigorous. You would need to specify<BR/>the proof system that you allow<BR/>proofs that partial orders have<BR/>width w to be in. <BR/>YES this could be interesting<BR/>(might depend on the answer).<BR/>I do not believe it has been worked on but you should ask<BR/>the FOM website (Foundations of<BR/>Math).<BR/><BR/>ALSO of interest- the REVERSE MATH<BR/>program which also looks at<BR/>the question of how nonconstructive<BR/>a theorem is in a different<BR/>framework.<BR/><BR/>bil gasarchAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-56378416062565181772009-01-30T16:35:00.000-06:002009-01-30T16:35:00.000-06:00The theorem you quote as desired, gets w as is wit...The theorem you quote as desired, gets w as is with no computable justification. <BR/> <BR/>It seems to me that to consider a truly computable version, the input should contain a proof that the machine induces a partial order of width w.<BR/><BR/>Is there a reason my intuition is wrong? <BR/>Is something known about that?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-39388627994666732722009-01-30T11:55:00.000-06:002009-01-30T11:55:00.000-06:00This article could use a little editing...This article could use a little editing...sep332https://www.blogger.com/profile/15089674288837329342noreply@blogger.com