부울 표현의 최소화 NP가 완성됩니까?

StackOverflow https://stackoverflow.com/questions/600068

문제

부울 만족성이 NP가 완성된다는 것을 알고 있지만 부울 표현의 최소화/단순화는 상징적 형태로 주어진 표현을 취하고 상징적 형태 인 NP- 완성 된 동등하지만 단순화 된 표현을 생성한다는 것을 의미합니다. 만족도에서 최소화로의 감소가 있는지 확실하지 않지만 아마도있을 것 같습니다. 누구든지 확실히 아는 사람이 있습니까?

도움이 되었습니까?

해결책

글쎄, 이런 식으로보십시오 : 최소화 알고리즘을 사용하면 문자 그대로의 만족할 수없는 표현을 압축 할 수 있습니다. false, 오른쪽? 이것은 SAT를 효과적으로 해결합니다. 따라서 최소한 완전한 최소화 알고리즘이 NP- 완성 NP 하드.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top