Аннотация:
Рассматриваются классы систем булевых уравнений без ограничений на выбор неизвестных (классы вида $[F]_{NC}$). Известна теорема разделимости Т. Шефера (Т. Schaefer, 1978) о том, что задача распознавания совместности систем таких классов является либо полиномиальной, либо NP-полной, и это определяется шестью свойствами порождающего набора булевых функций $F$.
В докладе будут представлены дальнейшие исследования сложности решения систем рассматриваемых классов. Доказаны теорема разделимости для задачи распознавания совместности систем классов $[F]_{NC}$ при исключении тривиальных решений и теорема разделимости для задачи определения числа решений систем классов $[F]_{NC}$. Значительное место в докладе будет уделено изучению множеств булевых функций, порождающих полиномиально решаемые классы систем булевых уравнений без ограничений на выбор неизвестных.
|
