Я прочёл пост и почти всё понял, что невозбранно подняло моё ЧСВ.
> исходная формула имеет удовлетворяющую подстановку тогда и только тогда, когда m-тая смешанная производная этого многочлена (по всем переменным) отлична от нуля. Интересное утверждение. Из чего оно следует? Можете доказать?
И да, за что вы обзываете элементарный дизъюнкт клашем? :)
Кэп идёт на помощь_winnieNovember 12 2010, 23:54:02 UTC
У меня ушло полчаса что бы врубиться. Хотя когда поймёшь, начинает казаться очевидным.
Переходим от такой формы записи A: (a|!b|!c) B: (a|!b|c) C: (!a|!b|!c) D: (!a|!b|c) E: (a|b|c) F: (!a|b)
к такой, где для каждого "атома" x и !x записано, в каком наборе клауз он встречается:
a: A, B, E - набор для a !a: C, D, F - набор для !a b: E, F - набор для b и тд. для !b, c, !c
Теперь что бы понять, дают ли конкретные значения "атомов" (a, !a, b, !b, c, !c) результат формулы 0 или 1 надо объединить все те наборы клауз, которые соответствуют "атомам" равным 1. Если исходная SAT-формула дала 1, значит A=B=C=D=E=F=1, значит объединение наборов по единичным "атомам" дало набор {A,B,C,D,E,F}.
Теперь забываем, что A,B,C,D,E,F были клаузами (конъюнктами), теперь думаем только о том, будет при некотором значении атомов объединение наборов с единичным атомами равно ABCDEF.
(ABE+CDF)(EF+ABCD)(BDE+AC) - это такой способ записать все возможные варианты наборов. Объединение можно записать как умножение, напр. AB*BC это AB2C, на двойку забиваем
( ... )
> исходная формула имеет удовлетворяющую подстановку тогда и только тогда, когда m-тая смешанная производная этого многочлена (по всем переменным) отлична от нуля.
Интересное утверждение. Из чего оно следует? Можете доказать?
И да, за что вы обзываете элементарный дизъюнкт клашем? :)
Reply
> Каждому возможному набору значений переменных k-SAT формулы соответствует ровно один моном.
> Удовлетворяющим подстановкам соответствуют мономы, содержащие все переменные многочлена
ЧВС тонкая штука да :-\
Reply
Переходим от такой формы записи
A: (a|!b|!c)
B: (a|!b|c)
C: (!a|!b|!c)
D: (!a|!b|c)
E: (a|b|c)
F: (!a|b)
к такой, где для каждого "атома" x и !x записано, в каком наборе клауз он встречается:
a: A, B, E - набор для a
!a: C, D, F - набор для !a
b: E, F - набор для b
и тд. для !b, c, !c
Теперь что бы понять, дают ли конкретные значения "атомов" (a, !a, b, !b, c, !c) результат формулы 0 или 1 надо объединить все те наборы клауз, которые соответствуют "атомам" равным 1. Если исходная SAT-формула дала 1, значит A=B=C=D=E=F=1, значит объединение наборов по единичным "атомам" дало набор {A,B,C,D,E,F}.
Теперь забываем, что A,B,C,D,E,F были клаузами (конъюнктами), теперь думаем только о том, будет при некотором значении атомов объединение наборов с единичным атомами равно ABCDEF.
(ABE+CDF)(EF+ABCD)(BDE+AC) - это такой способ записать все возможные варианты наборов.
Объединение можно записать как умножение, напр. AB*BC это AB2C, на двойку забиваем ( ... )
Reply
Reply
Ну ээ, я просто не особенно владею русскоязычной терминологией. А словечко "клаш" я увидел у Разборова, в его рецензии на работу какого-то неудачника.
Reply
Reply
Leave a comment