Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия, Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки
О факторизации, диофантовых уравнениях и сведении задач
21.07.2009, 20:43
Известно, что задача факторизации сводится к задаче ВЫПОЛНИМОСТЬ. Пытался разобраться в NP-лексике и у меня вопрос возник - правильно ли понимаю, что для доказательства принадлежности факторизации к классу NP-полных задач необходимо обратное сведение от любой NP-полной, например от ВЫПОЛНИМОСТЬ, к факторизации? К каким еще задачам сводится задача факторизации, и наоборот? Известно ли, что факторизация сводима к задаче о разрешимости-неразрешимости некоторого диофантового уравнения второй степени с двумя неизвестными, а также к задаче о четности-нечетности решения некоторого подобного уравнения с гарантированно единственным решением? Какова может быть сложность этих двух задач?
maxal
Re: О факторизации, диофантовых уравнениях и сведении задач