9
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ @D.W. No, just self reducibility. Read the paper. $\endgroup$
    – Yuval Filmus
    Nov 21, 2015 at 13:54

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks! Quick question though, was my understanding of the main part of their proof correct, or did I not follow it properly? We haven't done much with actual formal language definitions, we've been a little more abstract so it's hard to feel confident in this level of detail. (Also just going to wait a bit to accept the answer since I have minimal subject matter knowledge and would like to wait to see if others chime in.) $\endgroup$
    – Adam Martin
    Nov 21, 2015 at 15:23
  • $\begingroup$ If a problem is self-reducible in the sense of Schnorr and the decision version can be solved in polynomial time, then you can find the lexicographically first solution in polynomial time. This rests on the particular definition of Schnorr. In this case the decision version is very easy (the answer is always YES) whereas the lex-first version is NP-hard, so the problem is not self-reducible unless P=NP. $\endgroup$
    – Yuval Filmus
    Nov 21, 2015 at 15:26
  • $\begingroup$ Thanks! I feel like the only stumbling block I still have is the different senses of self-reducibility. Should I ask another question, or is it a minor enough distinction I can ask for it here/edit my original? We learned kind of broadly that a problem is self-reducible if given a polytime existence solution you can create a polytime search solution. Is there a technical distinction here that this result is dependant on? $\endgroup$
    – Adam Martin
    Nov 21, 2015 at 15:34
  • 1
    $\begingroup$ Take a look at the paper of Große et al., which discusses this point. $\endgroup$
    – Yuval Filmus
    Nov 21, 2015 at 15:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.