태그 보관물: relativization

relativization

coNP와 NP를 분리하는 오라클 같은 oracle 있고 와 같은

증명하는 방법 ? 나는 단지 oracle TM 과 이것이 재귀 언어 을 찾고 있습니다.

NPA≠coNPA

M

L(M)=L

와 같은 oracle 있고 와 같은 oracle 가 있음을 증명하는 증거를 알고 있습니다. . 나는 의 증거를 확장하여 그러한 오라클 를 찾아야한다는 힌트를 얻었지만 검색하고 읽을 때마다 어디에서나 “명확한”또는 “직선적”이지만 나는 그것을 어떻게 증명하는지 전혀 모른다.

A

PA≠NPA

A

PA=NPA

A

PA≠NPA


답변

Max가 수정이 어렵지 답변의 나머지 부분을 읽지 않고 문제에 대해 조금 더 생각할 것을 제안합니다. 수정이 필요하고 의 정의를 기억하는 부분은 하나 machine accepts는 해당 부분을 수정하는 데 도움이됩니다.

coNP

아래에서 필요한 수정을 설명하지만 먼저 원본 증명을 간략하게 살펴 보겠습니다.

원래 증거에서 단계에서 단계에 내장되어 확인하여 해당 에 일 기계 , 언어를 결정하지 않습니다 올바르게. 세트는 있습니다. i i P M i { x y A | x | = | y | } N P A

A=⋃nAn

i

i

P

Mi

{x∣∃y∈A |x|=|y|}

NPA

우리는 시뮬레이션하여이를 부분 사용 우리가 구축 한 어디에 충분히 큰이 (문자열이 이전 단계에서 고려 문자열보다 긴)입니다. 우리가 길이의 문자열을 추가 거부 할 경우 우리는 아무것도 추가하지 마십시오, 수용 것을 세트에 쿼리를 (하지 않습니다이 길이의 기하 급수적으로 많은 문자열 때문에 이러한 문자열은 존재 있지만 에 대한 질문 수 없습니다 다항식 시간에 모두). 향후 단계에서 의이 부분을 수정하지 않습니다 (예 : 길이가 이하인 문자열은 동일하게 유지됨). 이것은 A 0 m m M i m M i m M i A m M A i

Mi

A

0m

m

Mi

m

Mi

m

Mi

A

m

MiA

는 언어를 올바르게 결정하지 않고 증거를 완성합니다.

이제 머신 가 대신 에 있다고 가정하십시오 . 가 인식하지 못하도록 증명을 수정해야합니다 . 수락하면 를 이전과 동일 하게 유지 하고 모든 것이 원래 증거 에서처럼 잘 작동합니다. 거부되면 문자열이 세트에 추가되어 올바르게 응답하지 않는지 확인해야합니다. 우리는 여전히 의 일부로 를 시뮬레이션 할 수 있습니다 . 문제는 가 길이가 모든 문자열을 쿼리 할 수 있다는 것 입니다. 여기서 머신의 작동 방식이 중요해졌습니다. 모든 경우에 한해 받아들입니다c o N P P M A i L A M i A M i n c o N P m A

Mi

coNP

P

MiA

L

A

Mi

A

Mi

n

coNP

계산 경로가 허용됩니다. 이 경우 거부되므로 거부하는 계산 경로가 있습니다. 이 경로를 그대로 유지하면 모든 것이 작동하므로 해당 경로의 쿼리에 대한 답변을 동일하게 유지하면됩니다. 이 경로의 쿼리 수는 다항식입니다 (기계가 다항식 시간으로 실행되기 때문에) . 경로에 대해 쿼리하지 않는 길이가 문자열이 있습니다.이 중 하나를 추가 하면 나머지 증거는 전에.

m

A

단계는 알고리즘 방식이므로 세트 는 재귀 적입니다 (구성의 필수 부분은 에서 수행 할 수있는 기계를 시뮬레이션 할 수 있음 ).D S p a c e ( n ω ( 1 ) )

A

DSpace(nω(1))

답변

Christos Papadimitriou의 Computational Complexity 텍스트를 참조 할 수도 있습니다 . 특히 14 장 3 절에서 오라클을 탐구합니다. 예를 들어 일부 orales 및 경우 및 대한 증명 이 자세히 제공되며 주요 문제에 도움이 될 수 있습니다. 희망이 도움이됩니다.P BN P B A B

PA=NPA

PB≠NPB

A

B

답변