2
두 가지 NP 완성 문제의 차이점은 무엇입니까? 부울 수식이 만족 될 수 있는지 (즉, 출력 1), 하나는 회로의 컨텍스트에 있고 다른 하나는 수식에 해당하는지 묻는 것입니다. 그러나 부울 회로에서 부울 수식을 쓸 수는 없었습니까?C-SAT와 SAT의 차이점은 무엇입니까?
A
답변
1
맞아요, 그들은 서로 아주 가깝습니다. 모든 C-SAT 문제는 SAT로 표현 될 수 있으며 모든 SAT 문제는 C-SAT로 표현 될 수 있습니다. C-SAT < -> SAT를 가장 효율적인 방법으로 번역하는 방법에 대한 질문이 있습니다. 어떤 과제는 SAT로 표현하는 것이 더 낫습니다. 그 중 일부는 C-SAT보다 우수합니다.
또한 인기있는 절제 형식 대신 회로 표현을 내부적으로 사용하는 SAT 해결사가 있습니다.
또한이 훌륭한 설문지를 읽을 수 있습니다. M. Bjork, 2009, Successful SAT encoding techniques