CODEWITHSUNDEEP
algorithmcomplexity-theorynp
Shrey
Shrey

Reputation: 532

Reduction between problems in NP

By definition, any problem in NP can be reduced to a problem in NP-Complete. However, let's say we have two arbitrary problems X and Y in NP. Is it necessarily true that X is reducible to Y?

I'm unclear on the aspect of reduction between two arbitrary problems of a particular complexity class, so any guidance would be appreciated.

Upvotes: 0

Views: 292

Answers (1)

btilly
btilly

Reputation: 46409

In principle there is no reason why an arbitrary problem should be reducible to another.

For a concrete example, it is known that factorization of an arbitrary integer with n bits is in NP, but it is is believed to both not be in P and not to be NP-complete. Therefore traveling salesman is not reducible to integer factorization.

https://en.wikipedia.org/wiki/NP-intermediate has a list of other problems that are in the same category, and there is no reason to believe that, for example, graph isomorphism is reducible to factoring or vice versa.

Upvotes: 2

Related Questions