Положу тут
https://arxiv.org/pdf/cond-mat/0408190.pdf
Пусть лежит.
Я её четвёртый раз перечитываю, каждый раз новую пищу для ума нахожу. Правда, наткнулся я на неё в середине недели, поэтому до конца осмыслить не успел.
Это статья про конструирование сложных задач для проверки алгоритмов решения задач логической выполнимости. Там конструируются задачи специального вида на основе гамильтониана спиновых стёкол и сравниваются с задачами, созданными по случайному выбору 3-XOR ограничений. Для одного из алгоритмов (record-to-record - вот хрен, где найдёте, а там есть) подбирают параметр, что позволяет более быстро получать решения, что для случайных 3-XOR, что для этих вот спиновых стёкол.
Да, "гамильтониан спиновых стёкол" это просто произведение (Логическое И) 3-XOR ограничений "рядом" стоящих переменных, из которых можно образовать треугольник. Звучит страшно, вот и всё. ;)
Пусть лежит.
Я её четвёртый раз перечитываю, каждый раз новую пищу для ума нахожу. Правда, наткнулся я на неё в середине недели, поэтому до конца осмыслить не успел.
Это статья про конструирование сложных задач для проверки алгоритмов решения задач логической выполнимости. Там конструируются задачи специального вида на основе гамильтониана спиновых стёкол и сравниваются с задачами, созданными по случайному выбору 3-XOR ограничений. Для одного из алгоритмов (record-to-record - вот хрен, где найдёте, а там есть) подбирают параметр, что позволяет более быстро получать решения, что для случайных 3-XOR, что для этих вот спиновых стёкол.
Да, "гамильтониан спиновых стёкол" это просто произведение (Логическое И) 3-XOR ограничений "рядом" стоящих переменных, из которых можно образовать треугольник. Звучит страшно, вот и всё. ;)