Учитывая логическое выражение, выполнимо ли оно, когда максимум 42 переменных равен 1, а остальные переменные равны 0?
Я почти уверен, что проблема в NP, потому что вы можете угадатьприсваивание переменных, где максимум 42 равны 1, и проверьте, удовлетворено ли выражение.Так что я предполагаю, что проблема, скорее всего, NP-сложная, но я не уверен, как это показать.Обычно мы уменьшаем 3SAT, SAT или n-Clique, чтобы показать, что что-то является NP-сложным, но с этой проблемой я совершенно не представляю, как это сделать.
Я пробовал это с n-Clique, так что яполучить DNF со всеми кликами.Поскольку одна клика должна состоять максимум из 42, одна клика может быть установлена в 1, и выражение удовлетворяется.Однако я не смог получить клики за полиномиальное время, так как он в NP.