4446
правок
Irina (обсуждение | вклад) м (→Нотация) |
Irina (обсуждение | вклад) |
||
Строка 25: | Строка 25: | ||
Тривиальный алгоритм перебора, перечисляющий все возможные присваивания n переменным, выполняется за <math>2^n</math> шагов с полиномиальным временем. Таким образом, <math>\alpha \le 2</math>; по тривиальной причине <math>\beta, \gamma \le 2</math>. В начале 80-х Мониен и Спекенмейер заметили, что <math>\beta</math> можно сделать меньше. ''//И они, и другие исследователи также отметили, что | Тривиальный алгоритм перебора, перечисляющий все возможные присваивания n переменным, выполняется за <math>2^n</math> шагов с полиномиальным временем. Таким образом, <math>\alpha \le 2</math>; по тривиальной причине <math>\beta, \gamma \le 2</math>. В начале 80-х Мониен и Спекенмейер заметили, что <math>\beta</math> можно сделать меньше. ''//И они, и другие исследователи также отметили, что <math>\alpha</math> можно сделать меньше для специального случая задачи, в котором длина каждого дизъюнкта ограничена константой; соответствующие ссылки и алгоритмы см. в статье «[[Алгоритмы локального поиска для k-КНФ]]».//'' | ||
Затем Куллманн и Лукхардт [12] разработали схему для алгоритмов SAT типа «разделяй и властвуй» ''//также называемых DPLL в связи со статьями Дэвиса и Патнем [7] и Дэвиса, Логемана и Лавленда [6]//'', которая разбивала исходную задачу на несколько (как правило, постоянное число) подзадач, подставляя значения некоторых переменных и упрощая полученные формулы. В результате этого исследования были получены следующие верхние пределы для <math>\beta</math> и <math>\gamma</math>: | Затем Куллманн и Лукхардт [12] разработали схему для алгоритмов SAT типа «разделяй и властвуй» ''//также называемых DPLL в силу его связи со статьями Дэвиса и Патнем [7] и Дэвиса, Логемана и Лавленда [6]//'', которая разбивала исходную задачу на несколько (как правило, постоянное число) подзадач, подставляя значения некоторых переменных и упрощая полученные формулы. В результате этого исследования были получены следующие верхние пределы для <math>\beta</math> и <math>\gamma</math>: | ||
Строка 40: | Строка 40: | ||
<math>T(F) \le \sum_{i=1}^k T(F'_i) + const,</math> | <math>T(F) \le \sum_{i=1}^k T(F'_i) + const,</math> | ||
давало желаемую верхнюю границу по количеству листьев в дереве рекуррентности и, следовательно, по времени работы алгоритма. В частности, для получения границы <math>|F|^{O(1)} \cdot 2^{0,30897m} | давало желаемую верхнюю границу по количеству листьев в дереве рекуррентности и, следовательно, по времени работы алгоритма. В частности, для получения границы <math>|F|^{O(1)} \cdot 2^{0,30897m}</math> необходимо решить либо две подзадачи F[x], F[<math>\lnot</math>x] с рекуррентным неравенством | ||
<math>t_m \le t_{m - 3} + t_{m - 4}</math> | <math>t_m \le t_{m - 3} + t_{m - 4}</math> | ||
Строка 48: | Строка 48: | ||
<math>t_m \le 2t_{m - 6} + 2t_{m - 7},</math> | <math>t_m \le 2t_{m - 6} + 2t_{m - 7},</math> | ||
где <math>t_i = max_{m(G)\le i} T(G)</math>. Правила упрощения, используемые в алгоритмах со временем выполнения <math>|F|^{O(1)} \cdot 2^{0,30897m} | где <math>t_i = max_{m(G)\le i} T(G)</math>. Правила упрощения, используемые в алгоритмах со временем выполнения <math>|F|^{O(1)} \cdot 2^{0,30897m}</math> и <math>|F|^{O(1)} \cdot 2^{0,10299l}</math>, выглядят следующим образом. | ||
правок