Кодировка Atleast K из N в решателях SAT

Question

Я знаю, что, имея инструмент не более k из N, я могу получить не менее K из N, изменив его на максимум (nk) из N.

Но я не могу показаться чтобы обернуть голову вокруг, как это правда. Я мог бы упустить что-то очень тривиальное

Например, если K = 2 и N = 6, как минимум 2 из 6 эквивалентны максимум 4 из 6

любая помощь будет оценили

Answer 1

Как вы говорите, эквивалентность просто не соответствует действительности. Так что не расстраивайтесь из-за того, что не понимаете этого. Чтобы увидеть, давайте возьмем пример. Допустим, у нас есть только логические значения, N = 6 и K = 2, и присваивание:

True False False False False False

этим 6 переменным. Утверждение At most 2 out of 6 are True, очевидно, удовлетворено этим назначением, но At least 4 out of 6 are True - нет.

Возможно, вы имели в виду:

по крайней мере, K из N - True

эквивалентно

не более чем NK из N равно False

, что можно обобщить следующим образом:

не менее K из N объектов имеют свойство P

эквивалентно:

не более NK из N объектов не иметь свойство P

Это то, что вы пытались express? Надеюсь, это более понятно!