О факторизации, диофантовых уравнениях и сведении задач

[dmd]

Известно, что задача факторизации сводится к задаче ВЫПОЛНИМОСТЬ. Пытался разобраться в NP-лексике и у меня вопрос возник - правильно ли понимаю, что для доказательства принадлежности факторизации к классу NP-полных задач необходимо обратное сведение от любой NP-полной, например от ВЫПОЛНИМОСТЬ, к факторизации?
К каким еще задачам сводится задача факторизации, и наоборот?
Известно ли, что факторизация сводима к задаче о разрешимости-неразрешимости некоторого диофантового уравнения второй степени с двумя неизвестными, а также к задаче о четности-нечетности решения некоторого подобного уравнения с гарантированно единственным решением? Какова может быть сложность этих двух задач?

[maxal]

см.
Н. П. Варновский. Проблема P =? NP, классы сложностей и криптография

[goldbash]

Цитата:

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

А разве алгоритм Шора не означает, что задача факторизации принадлежит к классу P?

[maxal]

goldbash в сообщении #233231 писал(а):

А разве алгоритм Шора не означает, что задача факторизации принадлежит к классу P?

Нет. Наличие алгоритма Шора означает принадлежность задачи факторизации к классу BQP:
http://en.wikipedia.org/wiki/Quantum_co ... ity_theory

[goldbash]

Цитата:

Алгоритм отождествляется с детерминированной машиной Тьюринга

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