If you want to make money online : Register now

[Solved]: What NP decision problems are not self-reducible?

, , No Comments
Problem Detail: 

So we just learned about self-reducibility in class. My professor and our textbook would not commit to saying that all problems in NP are self-reducible, but there didn't seem to be any examples of problems that are not. I was wondering if there are any examples, or if it's just a situation where you can't prove a negative easily. Wikipedia only says It is conjectured that the integer factorization problem is not self-reducible.

Googling found one result, which seems to state that planar graph 4 coloring is not self-reducible because LF-k coloring for a planar graph reduces to that reduction, but I couldn't quite follow the proof right now.

Is this an actual example of a self-reducibility disproof, and are there others?

Asked By : Adam Martin

Answered By : Yuval Filmus

The paper indeed shows that planar graph four coloring is not self-reducible in the sense of Schnorr. There are several other senses, under some of which every problem in P is self-reducible. See the follow-up paper of Große, Rothe and Wechsung. I am not aware of any other result of this kind. Going over all papers citing the paper you mention (this can be done using Google Scholar, for example), none give any such problems.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/49771

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback