5
부울의 만족도는 NP-Complete이지만 부울 표현식의 최소화/단순화라는 것을 알고 있습니다.이 표현식은 주어진 표현식을 상징적 형태로 가져 와서 상징 양식 NP-Complete에서 동등하지만 단순화 된 표현을 만드는 것을 의미합니다. 나는 satisfiability에서 최소화에 대한 감소가 있다는 것을 확신하지 못하지만, 아마 거기에있는 것처럼 느껴집니다. 아무도 확실히 압니까?부울 표현식의 최소화 NP 완료입니까?
조금 더 깔끔하게 작성하면 이것이 그가 찾던 감축 일 수 있습니다. –
당신과 원래의 포스터는 아마도 NP 하드를 의미합니다. 내가 알 수있는 한 문제는 NP에없는 것으로 알려져 있습니다. – starblue
starblue : 아니요, NP 완성을 의미합니다. SAT는 실제로 고전적인 NP 완전한 문제입니다. 즉, NP 완성으로 입증 된 첫 번째 문제 였고, 다른 모든 것은 직접 또는 간접적으로 그것으로 축소되었습니다. 그건 그렇고, 위키피디아의 기사에서 모두 설명되어 있습니다. –