Как называется класс математических задач?
Подскажите, если кто знает, буду благодарен.
Дана почти что обычная система линейных уравнений: Ax=b. Элементы A и b - целые числа. Нас интересуют такие решения, в которых все x_i равны 0 или 1. Хочется как-то описать структуру множества таких решений. Хотя бы их количество или существование.
Как эта задача называется? Я поискал по всем ключевым словам, какие придумал, но пока ничего не нашёл. Чем-то похоже на 0-1 integer linear programming, но проще. Что известно о сложности (NP-полна ли)? Какие у неё есть (если есть) "хорошие" частные случаи (типа вполне унимодулярной матрицы А или чего-нибудь ещё подобного)? (В моем случае про А довольно много всего известно, например, можно считать, что все элементы матрицы А тоже равны 0 или 1).
Дана почти что обычная система линейных уравнений: Ax=b. Элементы A и b - целые числа. Нас интересуют такие решения, в которых все x_i равны 0 или 1. Хочется как-то описать структуру множества таких решений. Хотя бы их количество или существование.
Как эта задача называется? Я поискал по всем ключевым словам, какие придумал, но пока ничего не нашёл. Чем-то похоже на 0-1 integer linear programming, но проще. Что известно о сложности (NP-полна ли)? Какие у неё есть (если есть) "хорошие" частные случаи (типа вполне унимодулярной матрицы А или чего-нибудь ещё подобного)? (В моем случае про А довольно много всего известно, например, можно считать, что все элементы матрицы А тоже равны 0 или 1).