-2
어딘가에 누군가 언젠가 P = NP라고 증명할 수있는 방법을 읽으면 다항식 시간에 문제를 풀 수 있다고 말할 수는 없습니다. 이유를 설명해 주시겠습니까?왜 P = NP는 다항식 시간에서 풀 수있는 튜링 기계의 정지를 암시하지 않습니까?
A
답변
3
정지 문제가 not solvable at all 인 것으로 판명 되었기 때문에.
속도 향상으로 분명히 해결하기가 쉽지 않습니다.
관련 문제
- 1. 튜링 기계의 정지가 정확히 무엇입니까?
- 2. 어떻게 튜링 기계의 속성은 간단하다 증명하기 위해
- 3. 반복 문자열에 대한 튜링 기계의 시간 복잡도
- 4. 어떤 튜링 기계 확장이 기계의 파워를 확장합니까?
- 5. 왜 이것이 잘못된 튜링 기계입니까?
- 6. 다항식 시간에서 해결하는 방법 미로 퍼즐에서 쥐?
- 7. 2 스택 PDA와 멀티 테루 튜링 기계의 장점
- 8. 튜링 머신을 어떻게 풀 수 있습니까? anbncn/n> = 1일까요?
- 9. 푸시 풀 왜 이런 방식으로 작동하지 않습니까?
- 10. 어떻게 다항식 시간에 파티션을 설정합니까?
- 11. 튜링 기계 명령 표
- 12. 왜이 다항식 추가가 작동하지 않습니까?
- 13. intellij가 "this"키워드를 암시하지 않음
- 14. 비 결정적 튜링 기계
- 15. 다항식 : 다항식
- 16. 보편적 인 튜링 기계 예
- 17. GMT 표준 시간에서 오프셋
- 18. 신뢰할 수있는 memcached 풀
- 19. 다항식 확장 : 다항식 계수와 x의 분리
- 20. 튜링 기계
- 21. 다항식
- 22. 다항식
- 23. 튜링 기계가 정식 계산 모델이 튜링 완료인지 결정할 수 있습니까?
- 24. UTC 시간에서 읽을 수있는 형식으로 haml 사용
- 25. 기계가 튜링 기계와 동일한 지 확인하는 방법
- 26. /정지를 시작하는 방법/스레드
- 27. 왜 게시물을 삭제하지 않습니까?
- 28. LINEST를 통한 다항식 회귀
- 29. 비 결정적 튜링 기계가있는 상황에 맞는 언어
- 30. 튜링 머신에 DPDA?
Offtopic. 프로그래밍 문제가 아닙니다. 시도해보십시오. http://cs.stackexchange.com/ –
이 질문은 프로그래밍이 아니기 때문에 CS가 아닌 주제가 아닌 것으로 보입니다. CS 스택 교환 사이트를 사용해보십시오. – geoffspear
[기본 사항] (http://en.wikipedia.org/wiki/Halting_problem)에 익숙해 진 후에 [cs.stackexchange.com] (http://cs.stackexchange.com)을 사용해보십시오. 정지 문제 – HugoRune