Вопросы и ответе о криптовалюте
Означает ли apx Hard NP Hard?
Означает ли apx Hard NP Hard?
TaegeukChampionship
Sat Sep 14 2024
|
6
Ответы
1062
Не могли бы вы прояснить мне связь между «APX-hard» и «NP-hard» в контексте вычислительной сложности?
В частности, мне интересно, обязательно ли означает, что проблема, являющаяся APX-сложной, также является и NP-сложной.
Не могли бы вы подробнее рассказать о последствиях и потенциальных различиях между этими двумя классификациями и привести примеры, иллюстрирующие вашу точку зрения?
6 Ответы
Giulia
Mon Sep 16 2024
Отношения между NP и APX сложны, но интригуют.
На концептуальном уровне может возникнуть соблазн приравнять эти два понятия, но при более внимательном рассмотрении обнаруживаются их фундаментальные различия.
Эта информация была полезна?
128
93
MysticEchoFirefly
Mon Sep 16 2024
NP включает в себя набор задач решения, характеризующихся существованием верификаторов решений с полиномиальным временем.
И наоборот, APX инкапсулирует задачи оптимизации, целью которых является поиск лучшего решения среди набора возможных альтернатив.
Эта информация была полезна?
44
41
CryptoQueen
Sun Sep 15 2024
Несмотря на кажущиеся различия, NP и APX имеют тонкое взаимодействие.
Концептуально можно представить двунаправленный поток между этими двумя классами, позволяющий передавать идеи и методы из одной области в другую.
Эта информация была полезна?
264
94
TaegeukChampion
Sun Sep 15 2024
Эта связь становится очевидной при рассмотрении NP-полных задач решения.
Эти заведомо сложные проблемы, не поддающиеся эффективному решению, часто имеют соответствующие варианты оптимизации.
Эта информация была полезна?
112
31
Moonshadow
Sun Sep 15 2024
Однако эти аналоги оптимизации представляют собой еще более сложную задачу, попадая в категорию сложных APX.
Это обозначение означает, что они не только сложны по своей сути, но и противостоят алгоритмам аппроксимации, которые гарантируют почти оптимальные решения в разумные сроки.
Эта информация была полезна?
250
56
Загрузить еще 5 связанных вопросов
