Задача факторизации чисел относится к P или к PN?

[goldbash]

Хотелось бы просвятится по след. вопросу:

Все известные сейчас алгоритмы факторизации чисел на архитектуре Фон-Неймана имеют экспотенциальную сложность. С другой строны алгоритм Шора для квантовых компьютеров работает за полиноминальное время. Можно ли из этого заключить, что это задача класса P? И если так, то почему нельзя реализовать её за полиномиальное время на Ф-Н, или есть принципиальная связь между моделями вычисления и классами сложности?

[maxal]

см. topic24200.html