Схемная сложность дискретной оптимизации

Рассматривается подход к задаче минимизации линейной формы $(\tilde a,\tilde x)$, тносительно $\tilde x\in M\subset B_k^n$, где $M=\mathbf N_f=\{\tilde x\colon f(\tilde x)=1\}$, $f(\tilde x)$ – характеристическая функция – значной логики, входной вектор $\tilde a\in\mathbb R_n$. Для оценки сложности поиска оптимальной точки используется структурная характеристика множества $\mathbf N_f$, равная сложности схемного описания этого множества с помощью функциональных элементов в подходящих базисах, или сложность таких дескриптивных схем, описывающих $\mathbf N_f$, которым естественным образом сопоставляется оптимизационная схема той же сложности. Показано, что имеются существенные аналогии с задачами синтеза вычислительных схем из функциональных элементов, включая применимость аналогов методов теории управляющих систем к дискретной оптимизации. Во многих случаях подход естественным путем приводит к полиномиальным, хотя и необязательно наилучшим, алгоритмам, иногда за счет предварительной обработки входного вектора $\tilde a$. Статья является расширенным изложением доклада автора на IX Всесоюзной конференции по теоретической кибернетике.