Help with version of satisfiability problem

Правка en1, от tvan, 2021-03-06 19:24:20

During the latest USACO plat I managed to reduce the 2nd problem to the following:

You are given N restrictions and M truth/false variables. Restrictions are : given a1, a2... ak, at least one of them must be true for the restriction to be met ( so a1 or a2 or ... or ak == true). Each variable appears in at most 2 restrictions. What is the minimum number of variables which have to be true so that all restrictions are met?

Is there any (polynomial) solution to this problem ?

Теги minimum satisfiability

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский tvan 2021-03-06 19:24:20 532 Initial revision (published)