10
나는 P가 NP와 co-NP의 교차의 부분 집합이라는 것을 간단히 말한 몇 군데를 보았다. P가 NP의 하위 집합임을 나타내는 증명은 찾기 어렵지 않습니다. 따라서 그것이 교차점의 부분 집합이라는 것을 보여주기 위해서, P가 공동 NP의 부분 집합임을 보여 주면됩니다. 어떤 증거가 될 수 있겠습니까? 많이 고마워!왜 P ⊆ co-NP입니까?
A
답변
23
클래스 P은 보완 하에서 폐쇄 : L은 P의 언어 인 경우, L의 보완 P도이다. L에 대한 다항식 시간 결정자를 취하여 수용 및 거부 상태를 전환하여이를 볼 수 있습니다. 이 새로운 기계는 이제 L의 보수를 결정하고 다항식 시간에 그렇게합니다. 그 보완 NP에 IFF에
언어 L는 공동 에서 NP이다. 어떤 언어라도 고려하십시오 L ∈ P. L의 보수가 P도이므로, L의 보완 에 따라서 NP 인 (P 때문에 및 SUBSETEQ; NP). 따라서 L은 공동으로 NP입니다. 따라서 P & subseteq; co-NP.
희망이 도움이됩니다.
2
이렇게 생각하십시오. 클래스 co-P를 고려하십시오. P는 칭찬으로 닫혀 있기 때문에 P = co-P이다.
또한 P가 NP에 포함되어 있기 때문에 co-P가 co-NP의 하위 집합임을 분명히해야합니다. P = co-P이므로, P는 co-NP에 포함된다.
관련 문제
- 1. $ ('p'). remove(); 왜 안돼, 왜?
- 2. 왜</p> <p>Nodejs 코드, 부모가
- 3. P = NP 인 경우 왜 P = NP = NP- 완료입니까?
- 4. 왜 \ p {Lu}가 소문자와 일치합니까?
- 5. 왜 이런가/P ... 서버 업로드 실패
- 6. 왜
- 7. 왜 선언에서 int * p = NULL이라고 말합니까?하지만 테스트에서 p! = NULL입니다. 선언과 일치하는 이유는 * p! = NULL이 아니겠습니까?
- 8. * p ++와 * p ++ = * q
- 9. 왜
- 10. 왜 루비
- 11. 왜 오류
- 12. <p : selectOneMenu>의 Valuechangelistener는 작동하지만 예외가 발생합니다. 왜?
- 13. p : blockUI/pe : blockUI : 간단한 예제에서 왜 작동하지 않습니까?
- 14. 왜 Maven 프로파일을 활성화하려면 -P 대신 -D를 사용합니까?
- 15. scipy에서 p 값을 구하는 방법 chisquare : 왜 그런지 모르시겠습니까?
- 16. "set/p myvar = <file.txt"가 작동하지 않습니다 - 왜?
- 17. 왜 작동하지?
- 18. 목적 C는 ... 사람이 왜 알고 있나요 할당되어</p> <p>항목
- 19. 왜 내 자바 스크립트 함수가 호출되지되지 않은 MVC</p> <p>보기 작업
- 20. 왜 사후는 P (X = x | C = c_i) P (C = c_i)에 비례합니까?
- 21. gethostbyname까지도 한 번, h_errno에 왜 2</p> <p>
- 22. 왜 Threads의 ArrayList를 동기화해야합니까?</p> <p>메신저 만에이를 호출하는 경우
- 23. 왜 마우스의 p-> dx 및 p-> dy가 항상 0입니까?
- 24. 왜 파싱해야합니까? 내가 STH 좋아 한</p> <p>:
- 25. 는</p> <p>내가 상호 작용의 '부하'더 형태를하고있어 왜
- 26. 얻기의 URL PARAM은 <p></p> 왜 $ location.search.woNum가 내 컨트롤러 생성자에 정의되지 ... AngularJS와
- 27. jQuery를 복귀 ** 우리가 데이터를 사용하지 왜</p> <p>...
- 28. SQL을 사용하여 내가 왜 변수</p> <p>로 TABLENAME을 설정하려는
- 29. 왜 Ruby on Rails에서 Angular를 사용하고 싶습니까? 이제 ..</p> <p>을
- 30. Cakephp 왜 업데이트가 작동하지 않습니까? "</p> <p>:
저는 개인적으로이 질문에 관심이 없지만 다른 사람이 반대하면 http://cs.stackexchange.com –
에 질문 할 수도 있습니다.이 질문은 수학에 관한 주제이기 때문에 오프 토픽 인 것으로 보입니다. –