2014 dxdy logo

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

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




 
 Равенство классов P и NP - практическое применение
Сообщение15.08.2023, 21:37 
Предположим, что задача тысячелетия ''Равенство классов P и NP'' решена.
Где можно на практике применить алгоритм из этой задачи?
Нужно привести примеры, где он может быть использован.

 
 
 
 Re: Равенство классов P и NP - практическое применение
Сообщение15.08.2023, 21:50 
Аватара пользователя
Смотря в какую сторону и как. Есть довольно старый текст A personal view of average-case complexity, описывающий, что происходит в разных вариантах её решения.
konstr в сообщении #1605413 писал(а):
алгоритм из этой задачи
Понятия "алгоритм из задачи равенства P и NP" нет.

 
 
 
 Re: Равенство классов P и NP - практическое применение
Сообщение16.08.2023, 02:49 
Аватара пользователя
konstr в сообщении #1605413 писал(а):
Предположим, что задача тысячелетия ''Равенство классов P и NP'' решена.
Где можно на практике применить алгоритм из этой задачи?
Нужно привести примеры, где он может быть использован.
konstr в сообщении #1605411 писал(а):
Как понять гипотезу Ходжа (простыми словами с примерами)?
А с остальными задачами тысячелетия вам всё ясно?

 
 
 
 Re: Равенство классов P и NP - практическое применение
Сообщение17.08.2023, 13:54 
Аватара пользователя
Если будет доказано, что $P\ne NP$, то с практической точки зрения ничего особенно не изменится. Хотя можно считать практической пользой, что люди будут меньше времени тратить зря на некоторые безнадёжные занятия.
Если вдруг будет обнаружено, что $P=NP$, вероятно, во многих практических задачах будет бурный прогресс, появятся эффективные методы их решения, можно будет точно решать кучу задач, на данный момент неприступных. Хотя и тут могут быть варианты: если в найденных полиномиальных алгоритмах решения практических задач будут большие показатели степени, тогда на практике польза будет менее ощутимой.

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


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