2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

 
 
 
 Re: О факторизации, диофантовых уравнениях и сведении задач
Сообщение21.07.2009, 20:49 
Аватара пользователя
см.
Н. П. Варновский. Проблема P =? NP, классы сложностей и криптография

 
 
 
 Re: О факторизации, диофантовых уравнениях и сведении задач
Сообщение06.08.2009, 08:28 
Цитата:
правильно ли понимаю, что для доказательства принадлежности факторизации к классу NP-полных задач необходимо обратное сведение от любой NP-полной


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

 
 
 
 Re: О факторизации, диофантовых уравнениях и сведении задач
Сообщение06.08.2009, 08:32 
Аватара пользователя
goldbash в сообщении #233231 писал(а):
А разве алгоритм Шора не означает, что задача факторизации принадлежит к классу P?

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

 
 
 
 Re: О факторизации, диофантовых уравнениях и сведении задач
Сообщение06.08.2009, 12:51 
Цитата:
Алгоритм отождествляется с детерминированной машиной Тьюринга


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

 
 
 [ Сообщений: 5 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group