tag:blogger.com,1999:blog-3722233.post1079245433103531373..comments2024-10-08T07:31:09.455-05:00Comments on Computational Complexity: Is Immunity Interesting?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-3722233.post-13266606731823613472017-03-07T12:32:57.883-06:002017-03-07T12:32:57.883-06:00Professor GASARCH, Is it proved that NP is not P-i...Professor GASARCH, Is it proved that NP is not P-immune or not UP-immune? Or maybe is that a trivial result? In case it would be non-trivial, it might help us to understand better the NP class? Thanks in advance...Frank Vegahttps://www.blogger.com/profile/15257641208909866601noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-152312053558872582007-09-20T02:57:00.000-05:002007-09-20T02:57:00.000-05:00Is immunity interesting?Yes, for reality show cont...<I>Is immunity interesting?</I><BR/><BR/>Yes, for reality show contestants.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-77233006047037686222007-09-19T11:49:00.000-05:002007-09-19T11:49:00.000-05:00It is a good idea, in general, to see how strong a...It is a good idea, in general, to see how strong a result one can obtain in a given line of thought. For example, the idea of being hard-on-average (e.g., no algorithm from a class of algorithms has a significantly better chance than randomly guessing membership in a language) is one such idea, and is at the heart of pseudorandom generators via the hardness vs. randomness connection.<BR/><BR/>Another example, closer in spirit to what you mentioned, is almost-everywhere hardness (every algorithm for L takes more than T(.) time on all but finitely many inputs) -- this has been shown to be related to other versions of average-case complexity theory, which have connections to one-way functions, etc.<BR/><BR/>So, in summary: all of these ideas have value beyond being interesting intellectual exercises.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-19219089775020192552007-09-18T22:00:00.000-05:002007-09-18T22:00:00.000-05:00I'm still waiting for you to show us how to do the...I'm still waiting for you to show us how to do the bonus problem...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-81108634702900155582007-09-18T01:56:00.000-05:002007-09-18T01:56:00.000-05:00Unless I misunderstand the question (which is, of ...Unless I misunderstand the question (which is, of course, possible), I'd say it's "trivially interesting" - if the two sets don't differ infinitely often, a lookup table for inputs of size smaller than some N (the size of the largest different instance) will make the running time very similar.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-11870809062142620402007-09-17T20:31:00.000-05:002007-09-17T20:31:00.000-05:00I'm sure that the idea is used implicitly in all k...I'm sure that the idea is used implicitly in all kinds of settings. For example, any lower bound result, just because of the way lower bounds are defined, involves showing that a computation exceeds the resource bound infinitely often.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-80674102335985935162007-09-17T18:58:00.000-05:002007-09-17T18:58:00.000-05:00I don't know how "important" the idea of infinitel...I don't know how "important" the idea of infinitely-often is, but I does sometimes crop up in proofs when we can't prove what we'd "like" to. E.g., the result that non-trivial zero knowledge implies <EM>infinitely-often</EM> one-way functions.Anonymousnoreply@blogger.com