2SAT에서 긍정적 인 리터럴의 최대 수

문제

최대 2SAT는 NP 완료입니다.

최대 절을 만족시키는 대신, 나는 완전히 만족할 수있는 2sAT 공식을 가지고 있고, 나는 과제에 최대 긍정적 인 리터럴 수를 갖고 싶다 (예를 들어, 모든 조항이 만족되도록).

이 문제의 어려움은 무엇입니까?

해결책

이 문제는 최대 독립적 인 세트를 줄일 수 있기 때문에이 문제는 NP-HARD (및 대략적으로 대략적으로 어려운)가 필요합니다.감소 : 각 변수는 정점을 나타내고 각 절은 가장자리를 나타냅니다.

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 cs.stackexchange