2 가지 버전의 만족성 문제의 감속성을 튜링 할 수 있습니다

Question

이 문제에 도움이 필요합니다.

2 개의 버전의 만족성 문제가 있습니다 :

[1] 결정 버전 : 임의의 수식 F가 만족 스럽거나 아닌

[2] 검색 버전 : 임의의 수식 F가 만족할 만하면 반환 진리의 할당은 f를 만드는 수식에서 변수에 대한 변수에 대한 과제 만족스러운.F가 만족하지 않으면 NIL을 반환합니다.

은 [2]가 [1]으로 환원 할 수 있음을 보여줍니다.

[1]의 Oracle 알고리즘이 [2]의 "[2]가 [1]으로 환원하기 쉽다."라는 것을 수반한다는 것을 증명해야한다.

[2]는 임의의 수식 F의 만족 성을 차별하기 때문에 [1]의 Oracle 알고리즘 일뿐입니다.

[1]의 Oracle 알고리즘은 [2]의 Oracle 알고리즘을 수반 할 수 있습니까?할 수있는 경우, 이유는 무엇입니까?

Answer 1

공식의 만족 성을 결정하는 알고리즘을 사용하여 만족 가능한 공식에 대한 할당을 찾는 데 사용할 수 있습니다.

모든 변수가 할당되는 것은 아닙니다 :

• 변수를 선택하고 값 0을 선택합니다.

• 공식이 더 이상 만족할 수없는 경우 값을 1.

로 대체하십시오