tag:blogger.com,1999:blog-3722233.post7550599195743163827..comments2021-12-01T13:41:42.544-06:00Comments on Computational Complexity: Why are there so few intemediary problems in Complexity? In Computability?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-3722233.post-36051354625658492112014-03-28T17:44:02.685-05:002014-03-28T17:44:02.685-05:00If by "c.e.-complete" you are considerin...If by "c.e.-complete" you are considering completeness under many-one reductions, then there is one very natural (IMHO) intermediate problem, namely the set of Kolmogorov-compressible strings. Unfortunately, this single example does not apply to Turing reductions!Amir ben-Amramhttp://www2.mta.ac.il/~amirbennoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-2491744575647168262014-03-05T15:11:03.709-06:002014-03-05T15:11:03.709-06:00I think the the "Consistent Guessing Problem&...I think the the "Consistent Guessing Problem" discussed in Scott's blog http://www.scottaaronson.com/blog/?p=710 (see comment #15) could be<br />mentioned here? k-jlAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-66340312800220963932014-03-05T13:11:23.327-06:002014-03-05T13:11:23.327-06:00ps 2nd SVs opinion wish youd hang out more on tcs....ps 2nd SVs opinion wish youd hang out more on tcs.se but the <a href="http://meta.cstheory.stackexchange.com/questions/2791/to-some-of-the-elite-members-of-the-site" rel="nofollow">mere suggestion got shot down under heavy fire</a> =( ... perhaps ironically revealing some indications why sr researchers might <i>avoid</i> the site....vznhttp://vzn1.wordpress.comnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-7632716197377744242014-03-04T16:21:07.566-06:002014-03-04T16:21:07.566-06:00Could I ask what the following stand for?
* PC pro...Could I ask what the following stand for?<br />* PC problems<br />* NP-P<br />Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-50376355833859972322014-03-04T16:20:15.312-06:002014-03-04T16:20:15.312-06:00agreed they seem to be somewhat unusual. one wonde...agreed they seem to be somewhat unusual. one wonders if there is some undiscovered shaefer dichotomy-like theorem lurking somewhere. of course it will be better understood when P!=NP is proven. =)vznhttp://vzn1.wordpress.comnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-70697396432860334842014-03-04T11:58:03.821-06:002014-03-04T11:58:03.821-06:00You should visit cstheory more often :): http://cs...You should visit cstheory more often :): http://cstheory.stackexchange.com/a/237/80Suresh Venkatasubramanianhttps://www.blogger.com/profile/15898357513326041822noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16543435209862760482014-03-04T11:11:11.283-06:002014-03-04T11:11:11.283-06:00Obviously we have hit the "right" way of...Obviously we have hit the "right" way of determining the complexity of "natural" computational problems!Vijay Vaziranihttps://www.blogger.com/profile/17192690647930757263noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-58559084847757791202014-03-04T10:49:48.562-06:002014-03-04T10:49:48.562-06:00There are likely to be multiple reasons, not just ...There are likely to be multiple reasons, not just one. Here are a couple:<br /><br />- The exponential gap between unary and binary encoding length. One class of natural problems typically ignored when intermediate problems are discussed is based on NP-complete problems with pseudo-polynomial time algorithms like Subset-Sum. All you need is a bound on the sizes of integers that allows them to be bigger than polynomial but less than exponential. Requiring that the bounds on the sizes of the integers be either polynomial or exponential, which forcing encoding to be unary or binary does, could be considered artificial for such problems.<br /><br />- dichotomy theorems for constraint satisfaction. CSPs are a very natural way to describe many problems and are given many different names. This is very much a mathematical way of saying that intermediate problems of certain types do not exist.<br />Anonymousnoreply@blogger.com