0
일반적으로 우리는 NPC 문제가 있다고 가정합니다. 더 많은 제약 조건을 추가하면 (더 어렵게 만듭니다), 문제가 NPH가 될 수 있습니까? 나는 NPC와 NPH의 차이점을 안다. 그러나 기존의 NPC 문제에 새로운 제약 조건을 추가하는 것이 NPH가되거나 여전히 NPC로 남아 있음을 보여주는 방법을 모르겠다.NP 완성이 NP 하드 일 때
A
답변
1
NPC를 NPH 문제로 변환하는 추가적인 제한이있을 수 있습니다. 더 나아가 그것을 입증 할 수있는 사람이 세상에있을 수 없습니다.
관련 문제
- 1. 무언가를 증명하기 위해 NP 하드, 왜 NP 완성에서 그것을 줄일 필요가 있습니까? 위키
- 2. NP 문제입니까?
- 3. NP 문제입니까?
- 4. np 하드로 환원
- 5. NP 경도 경계
- 6. NP 검증기 기반 정의
- 7. np-hard-closure
- 8. NP-hard의 비주기적인 정의는 무엇입니까?
- 9. NP 완료 문제가 있습니까?
- 10. ggplot2를 사용하는 NP 차트
- 11. 증거 NP 완료
- 12. Np 경도 감소
- 13. 간단한 감소 (NP 완전성)
- 14. NP 최적화 문제 (정의)
- 15. TSP NP-Hard는 어떻습니까?
- 16. NP 패키지를 사용한 대역폭 선택
- 17. np-complete이지만 "hard"가 아닙니다.
- 18. 부울 표현식의 최소화 NP 완료입니까?
- 19. NP (Netscape) 웹 플러그인의 NSOpenGLView
- 20. Python np 배열 배열 배열
- 21. NP ++로 코드 서식 지정
- 22. NP 하드와 undecidable 문제 사이의 관계
- 23. 정지 문제가 NP 하드인지 증명 하시겠습니까?
- 24. NP 및 P로 문제를 생성해야하는 이유는 무엇입니까?
- 25. NP 완전하다고 의심되는이 문제를 나타내는 모델을 찾으십시오.
- 26. 이 데이터 공유 문제는 NP 문제입니까?
- 27. NP에서도 모든 NP-Easy 문제가 있습니까?
- 28. NP 완성 <p>NP에 있는지 여부에 관계없이 문제 B에 대해서는 아무 것도 표시되지 않습니다. 나는 Hopcraft와 Ullman 책에서 NP 완성 문제 P1이 다항 적 시간에 P2 문제로 축소 될 수 있고 P2가 NP 완성이면 정리가 있기 때문에 혼란 스럽다. 그러나 문제는 NP 클래스에 속해야한다는 NP 완성이라는 문제도 필요했습니다. 사람들은이 개념을 이해하는 데 도움을줍니다.</p>
- 29. '노드 배치'문제를 줄일 수있는 잘 알려진 NP 완성 문제가 있습니까?
- 30. NP Complete로 브랜드 지정되는 첫 번째 알고리즘은 무엇입니까?
감사합니다. Alex. 그것을 보여줄 문서 나 서류를 알고 있습니까? 나는 단지보기에 호기심이 많다. – Sara
죄송합니다, 종이는 없습니다. 추가적인 제약이 새로운 문제로 볼 수 있습니다. 새로운 문제는 해결하기가 더 어렵거나 쉽습니다. – AlexWien