0-1 программирование с постоянным числом ограничений полиномиально разрешимо?

В статье «Целочисленное программирование с фиксированным числом переменных» было показано, что целочисленное программирование с постоянным числом ограничений (или переменных) является полиномиально разрешимым.

Это относится к программированию 0-1?

Я предполагаю, что под «программированием 0-1 с постоянным числом ограничений» вы подразумеваете следующую проблему:

Максимизируйте некоторую линейную функцию (x_1, x_2, ..., x_n) с учетом ограничений, что каждый x_i находится в {0,1}, и постоянного числа дополнительных линейных ограничений.

Эта задача является NP-полной, даже с 1 дополнительным ограничением, поскольку в этой форме можно записать рюкзак 0-1.

В упомянутой статье Ленстра показал, что задача выполнимости целочисленной линейной программы

$A_{m,n}$$b \in \mathbb{Z}^m$
$x \in \mathbb{Z}^n$$Ax \le b$

полиномиально разрешима, если n или m постоянна. (Обратите внимание на отсутствие целевой функции.) Этот результат обычно используется при анализе параметризованных задач, т. Е. Он может быть использован для доказательства управляемости фиксированных параметров путем сокращения.

Целочисленное программирование 0-1 или двоичное целочисленное программирование (BIP) - это особый случай целочисленного программирования, где переменные должны быть 0 или 1 (а не произвольные целые числа). Эта проблема также классифицируется как NP-hard, и фактически версия решения является NP-Complete.

$k$$2^k$