4640
правок
Максимальная выполнимость формул в 2-КНФ: различия между версиями
Перейти к навигации
Перейти к поиску
Максимальная выполнимость формул в 2-КНФ (посмотреть исходный код)
Версия от 13:50, 25 марта 2025
, 25 март→Нотация
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 25: | Строка 25: | ||
Символы R и Z обозначают множества вещественных и целых чисел, соответственно. Буква | Символы <math>\mathbb{R}</math> и <math>\mathbb{Z}</math> обозначают множества вещественных и целых чисел, соответственно. Буква <math>\omega</math> обозначает наименьшее действительное число, такое, что для всех <math>\epsilon > 0</math> умножение матрицы размера <math>n \times n</math> над кольцом может быть выполнено за <math>О(n^{\omega + \epsilon})</math> кольцевых операций. В настоящее время известно, что <math>\omega < 2,376</math> [4]. Кольцевое матричное произведение двух матриц A и B обозначается как <math>A \times B</math>. | ||
| Строка 32: | Строка 32: | ||
k=l, ..., n | k=l, ..., n | ||
Несколько слов о m и n: применительно к графам они обозначают количество ребер и вершин графа, соответственно. В то же время в КНФ-формулах m и n обозначают количество дизъюнктов и переменных, соответственно. | Несколько слов о m и n: применительно к графам они обозначают количество ребер и вершин графа, соответственно. В то же время в КНФ-формулах m и n обозначают количество дизъюнктов и переменных, соответственно. | ||
== Основные результаты == | == Основные результаты == | ||