NZ
а не в виде строки
Size: a a a
2020 December 06
A
а именно 57 49 20 49 50 20 49 50 51
AT
Скажите пожалуйста, а NP-complete — это гипотеза? Есть ли тот алгоритм, который решение любой NP-complete приводит к решению другой NP-complete? Или это просто допущение?
AT
И там речь про именно алгоритм, который модифицирует алгоритм. Или про алгоритм, который модифицирует решение?
MK
Скажите пожалуйста, а NP-complete — это гипотеза? Есть ли тот алгоритм, который решение любой NP-complete приводит к решению другой NP-complete? Или это просто допущение?
Кажется все NP-complete сводятся друг к другу переформулировкой
MK
Или что-то такое
AT
То есть если я за неполиномиальное время найду конкретное решение одной задачи, то я "по изоморфизму" смогу его превратить в конкретное решение другой?
AT
и исходные данные тоже так же "маппятся"?
EZ
Скажите пожалуйста, а NP-complete — это гипотеза? Есть ли тот алгоритм, который решение любой NP-complete приводит к решению другой NP-complete? Или это просто допущение?
Это определение
A
ну то есть утверждение "данная задача является NP-полной" доказывается через утверждение вида "потому что если я смогу ее решать, то подобрав вот такие входные данные я получу решение вот такой известной NP-полной задачи"
AT
А, ну я нашёл https://en.wikipedia.org/wiki/List_of_NP-complete_problems . То есть это не гипотеза, а реально существующий класс с известными алгоритмами.
EZ
А, ну я нашёл https://en.wikipedia.org/wiki/List_of_NP-complete_problems . То есть это не гипотеза, а реально существующий класс с известными алгоритмами.
Хм и как же ты добрался до такого редкого неочевидного источника
AT
Есть эвристики для каждого алгоритма, наверное. Если собрать много эвристик и все преобразования одного алгоритма в другой из этого списка, то можно получить ускорения решений во многих случаях?
AT
Хм и как же ты добрался до такого редкого неочевидного источника
Ну зачем этот чат?) Понабрасывать)
MK
ну то есть утверждение "данная задача является NP-полной" доказывается через утверждение вида "потому что если я смогу ее решать, то подобрав вот такие входные данные я получу решение вот такой известной NP-полной задачи"
Ну я видел такие доказательства
EZ
Ну я видел такие доказательства
Кук Левин же
EZ
Не то чтобы я помню как его доказывать
EZ
Что-то в стиле "сэмулируй машину Тюринга sat'ом"
A
А значения переменных соответствуют недетерминированному выбору. Я видел, как сначала по МТ строится булева схема, а потом уже преобразуется в SAT.
A
я видел такое в статье блума/блума/шуба про генератор x^2 mod N - "пусть кто-то умеет восстановить эту последовательность. Тогда надо взять вот такое N и вот такое b0 и мы получим разложение N на простые множители"