4666
правок
Максимальная выполнимость формул в 2-КНФ: различия между версиями
Материал из WEGA
Максимальная выполнимость формул в 2-КНФ (посмотреть исходный код)
Версия от 06:07, 3 апреля 2025
, 3 апрель→Открытые вопросы
Irina (обсуждение | вклад) м (→Применение) |
Irina (обсуждение | вклад) |
||
| Строка 113: | Строка 113: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
• Необходимо улучшить использование памяти описанным выше алгоритмом. В настоящее время он требует <math>\Theta(2^{2n/3})</math>. Очень интересен пока нерешенный вопрос: существует ли алгоритм для MAX 2-SAT со временем <math>O(1,99^n)</math>, использующий только полиномиальный объем памяти. На этот вопрос можно было бы ответить положительно, если бы удалось найти алгоритм решения задачи о k-кликах (k-CLIQUE) с полилогарифмическими затратами памяти и временем <math>n^{k | • Необходимо улучшить использование памяти описанным выше алгоритмом. В настоящее время он требует <math>\Theta(2^{2n/3})</math>. Очень интересен пока нерешенный вопрос: существует ли алгоритм для MAX 2-SAT со временем <math>O(1,99^n)</math>, использующий только ''полиномиальный'' объем памяти. На этот вопрос можно было бы ответить положительно, если бы удалось найти алгоритм решения задачи о k-кликах (k-CLIQUE) с полилогарифмическими затратами памяти и временем <math>n^{k - \delta}</math> для некоторых <math>\delta > 0</math> и <math>k \ge 3</math>. | ||
• Хотелось бы найти алгоритм для MAX 2-SAT | • Хотелось бы найти алгоритм для MAX 2-SAT с временем выполнения менее <math>2^n</math>, не требующий быстрого умножения матриц. Алгоритмы быстрого умножения матриц имеют печальную репутацию непрактичных. | ||
• Следует обобщить вышеприведенный алгоритм для задачи MAX k-SAT, где k – любое целое положительное число. В текущей формулировке требуется эффективный алгоритм для нахождения малой гиперклики в гиперграфе. Однако для этой задачи неизвестны какие-либо результаты общего вида. Есть гипотеза, что для всех <math>k \ge 2</math> задача MAX k-SAT решается за время <math>\tilde{O}(2^{n(1 - \frac{1}{k + 1})})</math>, исходя из предположения, что умножение матриц выполняется за время <math>n^{2+o(1)}</math> [17]. | • Следует обобщить вышеприведенный алгоритм для задачи MAX k-SAT, где k – любое целое положительное число. В текущей формулировке требуется эффективный алгоритм для нахождения малой гиперклики в гиперграфе. Однако для этой задачи неизвестны какие-либо результаты общего вида. Есть гипотеза, что для всех <math>k \ge 2</math> задача MAX k-SAT решается за время <math>\tilde{O}(2^{n(1 - \frac{1}{k + 1})})</math>, исходя из предположения, что умножение матриц выполняется за время <math>n^{2+o(1)}</math> [17]. | ||
