2
일부 NP는 완성되었지만 "빠른"알고리즘을 알고있는 언어가 있습니까? 나는 평균적으로 잘 할 수있는 배낭과 같은 것을 의미하지는 않습니다. 즉, 최악의 경우에도 런타임은 2^n^엡실론과 같습니다. 결과는 엡실론> 0에 대해 유지되며 결과는 다음과 같습니다. 임의로 0에 가깝도록 허용하십시오.np-complete이지만 "hard"가 아닙니다.
A
답변
3
Wikipedia에 따르면 "NP 하드이지만 NP 완료가 아닌 결정 문제가 있습니다 (예 : 중단 문제)"
NP에서 "빠른"알고리즘을 알고있는 언어가 없습니다. 그렇지 않으면 NP 완료되지 않습니다.
3
이 np-complete 문제에 대한 "빠른"알고리즘을 발견했다면 방금 P = NP를 풀었습니다. 아시다시피 여전히 열린 질문입니다.
나는이 질문이 O (2^n^0.01) 시간에 쉽게 숙제 가능하다고 결정할 수 있었다. – msw
@msw : 소스를 제공하거나 롤백하십시오. – danben
@ 단벤 : 나는 농담을 잊어 버렸다. –