Этот вопрос не может быть техническим. Как не носитель языка и ТА для класса алгоритма, я всегда задавался вопросом, что означает гаджет в «гаджете-предложении» или «гаджете-переменной». В словаре говорится, что гаджет - это машина или устройство, но я не уверен, какое это имеет разговорное значение в контексте NP-полного доказательства.
cc.complexity-theory
np-hardness
terminology
reductions
Федерико Магалланез
источник
источник
Ответы:
«Гаджет» - это небольшое специализированное устройство для какой-то конкретной задачи. В NP-доказательствах твердости при выполнении сокращения от проблемы A к проблеме B разговорный термин «гаджет» относится к небольшим (частичным) экземплярам проблемы B, которые используются для «моделирования» определенных объектов в задаче A. Например, когда сокращая 3SAT до 3-COLORING, гаджеты предложений - это небольшие графики, которые используются для представления предложений исходной формулы, а гаджеты с переменными объектами - это небольшие графики, которые используются для представления переменных исходной формулы. Чтобы обеспечить правильное сокращение, гаджеты должны представлять собой графики, которые могут быть трехцветными совершенно определенным образом. Следовательно, мы рассматриваем эти маленькие графики как устройства, которые выполняют специализированную задачу.
Во многих случаях основной трудностью доказательства NP-твердости является создание соответствующих гаджетов. Иногда эти гаджеты сложные и в меру большие. Творческий процесс создания таких гаджетов иногда называют «гаджетом».
источник
Формальное определение гаджетов для сокращения оптимизации NP появляется здесь:
Л. Тревизан, Г. Б. Соркин, М. Судан, Д. П. Уильямсон. Гаджеты, аппроксимация и линейное программирование . SIAM J. по вычислительной технике, 29 (6): 2074-2097, 2000
источник