JК
ДИСКРЕТНАЯ МАТЕМАТИКА БЕЗ ФОРМУЛ :: Соловьев Александр
Страница: 70 из 71А проблему сложности вычислений математики выразили в виде формулы, которую все-таки приведу из-за ее краткости и «нетрудности» печати:
P = NP?
Интересно, говорят этой формулой математики, совпадаютли множество задач, решаемых за полиномиальное время и множество NP задач? Может просто толку пока не хватает найти простые решения…
Как бы там ни было, а задачи, для которых простые (полиномиальные) решения пока не найдены, существуют. И чем дальше, тем больше математики упорствуют в этой (недоказанной) уверенности. Более того, они коллекционируют типовые труднорешаемые задачи, которых уже набралось не менее тысячи. Более того, утверждают, что одни труднорешаемые задачи сводятся к другим труднорешаемым задачам. Поэтому даже используется для таких задач термин " NP –полные" задачи. И делается радикальное заявление: если хоть для одной NP –полной задачи будет найдено простое (полиномиальное) решение, тогда простое решение будет найдено и для всех остальных NP –полных задач.
P = NP?
Интересно, говорят этой формулой математики, совпадаютли множество задач, решаемых за полиномиальное время и множество NP задач? Может просто толку пока не хватает найти простые решения…
Как бы там ни было, а задачи, для которых простые (полиномиальные) решения пока не найдены, существуют. И чем дальше, тем больше математики упорствуют в этой (недоказанной) уверенности. Более того, они коллекционируют типовые труднорешаемые задачи, которых уже набралось не менее тысячи. Более того, утверждают, что одни труднорешаемые задачи сводятся к другим труднорешаемым задачам. Поэтому даже используется для таких задач термин " NP –полные" задачи. И делается радикальное заявление: если хоть для одной NP –полной задачи будет найдено простое (полиномиальное) решение, тогда простое решение будет найдено и для всех остальных NP –полных задач.