There are thousands of natural PC problems. Assuming P NE NP how many natural problems are there that are
in NP-P but are NOT NPC? Some candidates are Factoring, Discrete Log, Graph Isom, some in group theory, and any natural sparse set. See
here for some more.
A student asked me WHY there are so few natural intermediary problems. I don't know but here are some
options:
- Bill you moron, there are MANY such problems. You didn't mention THESE problems (Followed by a list of problems
that few people have heard of but seem to be intermediary.)
- This is a question of Philosophy and hence not interesting.
- This is a question of Philosophy and hence very interesting.
- That's just the way it goes.
- By Murphy's law there will be many problems that we can't solve quickly.
At least in complexity theory there are SOME candidates for intermediary sets.
In computability theory, where we know Sigma_1 \ne \Sigma_0, there are no
candidates for natural problems that are c.e., not decidable, but not complete. There have been some attempts to show that there can't be any
such sets, but its hard to define ``natural'' rigorously. (There ARE sets that are c.e., not dec, not complete, but they are
constructed for the sole purpose of being there. My darling would call them `dumb ass' sets,
a terminology that my class now uses as well.)
A long time ago an AI student was working on classifying various problems in planning. There was one that was c.e. and not decidable
and he was unable to show it was complete. He asked me to help him prove it was not complete. I told him, without looking at it,
that it was COMPLETE!!!!!!!!! My confidence inspired him to prove it was complete.
So, aside from the answers above, is there a MATH reason why there are so few
intermediary problems in Complexity, and NONE in computability theory?
Is there some other kind of reason?
There are likely to be multiple reasons, not just one. Here are a couple:
ReplyDelete- 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.
- 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.
Obviously we have hit the "right" way of determining the complexity of "natural" computational problems!
ReplyDeleteYou should visit cstheory more often :): http://cstheory.stackexchange.com/a/237/80
ReplyDeleteagreed 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. =)
ReplyDeleteCould I ask what the following stand for?
ReplyDelete* PC problems
* NP-P
ps 2nd SVs opinion wish youd hang out more on tcs.se but the mere suggestion got shot down under heavy fire =( ... perhaps ironically revealing some indications why sr researchers might avoid the site....
ReplyDeleteI think the the "Consistent Guessing Problem" discussed in Scott's blog http://www.scottaaronson.com/blog/?p=710 (see comment #15) could be
ReplyDeletementioned here? k-jl
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!
ReplyDelete