공개 질문 NP = co-NP는 P = NP와 동일합니까? 주요 공개 문제 라고 부르는 온라인의 여러

co- 를 주요 공개 문제 라고 부르는 온라인의 여러 장소를 기반으로 궁금한 점이 있지만 와 같은지 여부에 대한 표시를 찾을 수 없습니다. 문제 … $N P =$

N P =

$\sf NP=$ $N P$

N P

$\sf NP$ $P = N P$

P = N P

$\sf P=NP$

답변

아니요. 또 다른 공개 된 문제이며 확실히 관련되어 있지만 다릅니다. 복잡성 클래스 co- $N P$

N P

$\mathsf{NP}$ 는 보완이 인 언어 세트입니다 . 즉, “아니오”답변이 결정적 다항식 시간 검증기를 갖는 결정 문제 세트. 예를 들어 “이 SAT 수식이 만족스럽지 않습니까?”라는 질문이 있습니다. 대답이 “아니오”인 경우이를 증명하는 변수가 만족스럽게 할당됩니다. 이것이 검증 자의 인증서입니다. $N P$

N P

$\mathsf{NP}$

이 가능하다 , 아직 공동 . $P \neq N P$

P \neq N P

$\mathsf{P} \neq \mathsf{NP}$ $N P =$

N P =

$\mathsf{NP} =$ $N P$

N P

$\mathsf{NP}$

그러나 다른 한편으로, 이면 co- 입니다. 언어가 인 경우 보완은 도 있기 때문에 인 경우 모든 언어에 적용됩니다. 도 마찬가지입니다. $P = N P$

P = N P

$\mathsf{P} = \mathsf{NP}$ $N P =$

N P =

$\mathsf{NP} =$ $N P$

N P

$\mathsf{NP}$ $P$

P

$\mathsf{P}$ $P$

P

$\mathsf{P}$ $P = N P$

P = N P

$\mathsf{P} = \mathsf{NP}$ $N P$

N P

$\mathsf{NP}$

답변

이 질문에 대답하는 좋은 방법 중 하나는 다항식 계층 구조 (PH) 를 사용하는 것입니다 ( 여기 참조 ). 다항식 계층 구조는 , 및 클래스 를 oracle 컴퓨터로 일반화하고 문제의 복잡성을 측정 하는 척도 로 사용 하는 복잡성 클래스의 계층입니다 . $P$

P

${\sf P}$ $N P$

N P

${\sf NP}$ $c o - N P$

c o - N P

${\sf co-NP}$

만약 것으로 알려져있다 또는 다음 다항식 계층이 축소되어 첫 번째 레벨. $N P = c o - N P$

N P = c o - N P

${\sf NP}={\sf co-NP}$ $P = N P$

P = N P

${\sf P}={\sf NP}$

How IT

언제든지 물어보세요.

공개 질문 NP = co-NP는 P = NP와 동일합니까? 주요 공개 문제 라고 부르는 온라인의 여러

답변

답변

답변