undecidable 문제와 NP 어려운 문제 사이의 관계에 대해 조금 혼란스러워합니다. NP 하드 문제가 결정 불가능한 문제의 일부인지, 아니면 단순히 동일하고 동등한가요, 아니면 비교할 수없는 것입니까?NP 하드와 undecidable 문제 사이의 관계
나를 위해, 나는 결정할 수없는 문제가 NP 어려운 문제의 수퍼 세트라고 내 친구들과 논쟁 해왔다. NP에는 없지만 결정할 수없는 몇 가지 문제가 존재합니다. 그러나 나는이 주장이 약하고 혼란스러워하고 있음을 알고 있습니다. undocidable NP 완전한 문제가 있습니까? 결정할 수있는 NP 하드에 문제가 있습니까?
일부 토론은 큰 도움이 될 것입니다. 감사!
일부 입력에는 해결 불가능 = 해결할 수 없습니다. 알고리즘을 얼마 동안 (유한 한) 시간에 상관없이 어떤 입력에서는 항상 잘못 될 것입니다.
NP-hard ~ = 수퍼 다항식 실행 시간 (P! = NP라고 가정). 그것은 물결 모양이지만 기본적으로 NP-hard는 적어도 NP에서 가장 어려운 문제만큼 어렵다는 것을 의미합니다.
결정할 수없는 NP 하드 (확실히 결정할 수있는) 문제가 있습니다. NP 완성 문제는 그 중 하나 일 것입니다, 예를 들어 SAT.
NP 하드가 아닌 결정 불가능한 문제가 있습니까? 그렇게 생각하지는 않지만 그것을 배제하는 것은 쉽지 않습니다. SAT에서 가능한 모든 결정 불가능한 문제로 축소되어야한다는 명백한 주장은 없습니다. 그다지 이상하지 않은 결정할 수없는 이상한 문제가있을 수 있습니다. 그러나 결정할 수없는 표준 문제 (정지 문제, 말하자면)는 NP 어렵다.
NP-hard는 이상으로 적어도 인 NP 완전 문제와 마찬가지로 문제가됩니다.
따라서 결정 불가능한 문제는 NP 하드 일 수 있습니다. NP-hard는 NP-complete 문제를 쉽게 해결할 수있는 Oracle이 있다면 (즉, 다항식 시간에서 해결 가능) NP-hard입니다. 우리는 결정적인 문제를 생각해 볼 수 있습니다. 예를 들어, 주어진 NP를 해결할 수있는 NP 문제는 쉽게 해결할 수 있습니다. 예를 들어 분명히 의 모든 오라클은 NP 문제를 해결할 수 있습니다. 따라서 모든 Turing-complete 문제는 NP-complete를 해결할 수있는 (빠른) 오라클이라는 의미에서 NP-hard입니다. 문제는 산들 바람.
따라서 Turing-complete undecidable 문제는 NP-hard 문제의 하위 집합입니다.
누군가가 증거에서 "분명히"라고 말하면 경보 벨이 울리기 시작합니다. – OrangeDog
예를 들어 해결할 수없는 문제. 튜링 정지 문제는 NP 하드에만 해당됩니다. 작은 파이프 NP 및 NP-하드 어느 겹치는 것을 나타내고,이 도면에서
<---------NP Hard------>
|------------|-------------||-------------|------------|--------> Computational Difficulty
|<----P--->|
|<----------NP---------->|
|<-----------Exponential----------->|
|<---------------R (Finite Time)---------------->|
해결할 수없는 문제는 해결책이없고 NP가 아닌 NP 하드 문제입니다.
글쎄, 나는 결론에 도달 한 것으로 보인다. 결정 불가능한 문제는 NP 어려운 문제의 일부분이다. 이것은 다음 시나리오를 기반으로한다. NP의 모든 문제는 결정할 수있다. 결정할 수없는 NP 하드에는 몇 가지 문제가 있습니다 (결정할 수없고 NP 완성이라고 생각합니다). 따라서 결정 불가능한 문제는 NP의 하위 집합으로 구성됩니다. 내가 맞습니까? – akaHuman
"그러므로"나를 잃어 버렸습니다.확실히 봉쇄는 다른 방향으로 진행되지 않지만 두 세트는 비교할 수 없을 것입니다. 결정할 수없는 임의의 문제가 NP 하드 (즉, 폴리 시간에서 SAT를 해결하기 위해 오라클로 사용될 수 있음)에 있음을 증명해야합니다. –
오케이! 나는 거의 그것을 얻는 것처럼 보인다. – akaHuman