Сокращение между проблемами в NP

Question

По определению, любая проблема в NP может быть сведена к проблеме в NP-Complete . Однако, скажем, у нас есть две произвольные проблемы X и Y в NP . Обязательно ли X сводится к Y?

Мне неясен аспект сокращения между двумя произвольными задачами определенного класса сложности, поэтому любые указания приветствуются.

Answer 1

В принципе нет причин, по которым произвольная задача должна быть сведена к другой.

Для конкретного примера известно, что факторизация произвольного целого числа с n битами находится в NP, но считается, что оба не находятся в P и не являются NP -полными , Поэтому коммивояжер не сводится к целочисленной факторизации.

https://en.wikipedia.org/wiki/NP-intermediate содержит список других проблем, относящихся к той же категории, и нет оснований полагать, что, например, изоморфизм графов сводится к факторингу или наоборот.