NP 완전성

부울 만족도 문제(SAT)는 명제 공식(예시 설명)이 변수에 참 값을 적절히 할당함으로써 실현될 수 있는지 여부를 결정하도록 요청합니다.주어진 할당이 공식을 ^[1]참으로 만들지는 쉽게 확인할 수 있지만, 만족스러운 할당을 찾기 위해 모든 할당을 연속적으로 시도하는 것보다 기본적으로 더 빠른 방법은 없습니다.Cook과 Levin은 검증이 용이한 각 문제를 SAT만큼 빠르게 해결할 수 있다는 것을 증명했고, 따라서 NP-완전이다.

계산 복잡도 이론에서 문제는 다음과 같은 경우 NP-완전이다.

각 솔루션의 정확성을 신속하게 검증할 수 있고(다항식 시간 내에 확인), 브루트포스 검색 알고리즘은 가능한 모든 솔루션을 시도함으로써 해결책을 찾을 수 있는 문제입니다.
이 문제를 사용하여 다른 모든 문제를 시뮬레이트할 수 있으므로 솔루션이 올바른지 신속하게 확인할 수 있습니다.이러한 의미에서 NP-완전 문제는 솔루션을 신속하게 검증할 수 있는 가장 어려운 문제입니다.어떤 NP-완전 문제의 해결책을 빨리 찾을 수 있다면, 우리는 주어진 해결책을 쉽게 검증할 수 있는 다른 모든 문제의 해결책을 빠르게 찾을 수 있을 것이다.

"NP-complete"라는 이름은 "비결정론적 다항식 시간 완료"의 줄임말입니다.이 이름에서 "비결정론적"은 비결정론적 튜링 기계를 가리키며, 이는 무차별적인 검색 알고리즘의 개념을 수학적으로 공식화하는 방법입니다.다항식 시간은 결정론적 알고리즘이 단일 솔루션을 검사하거나 비결정론적 튜링 기계가 전체 검색을 수행하는 데 "빠른" 것으로 간주되는 시간을 말합니다."완전"은 동일한 복잡도 클래스의 모든 것을 시뮬레이션할 수 있는 속성을 의미합니다.

보다 정확하게 말하면, 문제에 대한 각 입력은 다항식 길이의 솔루션 집합과 관련지어져야 하며, 그 유효성을 신속하게(다항식 ^[2]시간 내에) 테스트할 수 있어야 하며, 따라서 솔루션 집합이 비어 있지 않으면 모든 입력에 대한 출력이 "예"이고 비어 있으면 "아니오"가 되어야 합니다.이 형식의 문제의 복잡도 클래스는 "비결정론적 다항식 시간"의 줄임말인 NP라고 불립니다.NP의 모든 것이 NP가 아니더라도 NP의 모든 것을 NP로 변환할 수 있다면 문제는 NP-hard라고 합니다. 반대로 NP와 NP-hard에 모두 있으면 NP-complete입니다.NP-완전 문제는 NP에서 가장 어려운 문제를 나타냅니다. 만약 일부 NP-완전 문제가 다항식 시간 알고리즘을 가지고 있다면, NP의 모든 문제는 그렇습니다.NP-완전 문제의 집합은 종종 NP-C 또는 NPC로 나타납니다.

NP-완전 문제의 해결 방법을 "빠르게" 검증할 수 있지만, 해결 방법을 신속하게 찾을 수 있는 방법은 없습니다.즉, 현재 알려진 알고리즘을 사용하여 문제를 해결하는 데 필요한 시간은 문제의 크기가 커짐에 따라 빠르게 증가합니다.결과적으로, P 대 NP 문제라고 불리는 이러한 문제들을 빨리 해결하는 것이 가능한지를 결정하는 것은 오늘날 컴퓨터 과학의 근본적인 미해결 문제 중 하나이다.

NP-완전 문제에 대한 해결책을 계산하는 방법은 빠르게 발견되지 않고 있지만, 컴퓨터 과학자와 프로그래머는 여전히 NP-완전 문제에 자주 직면합니다.NP-완전 문제는 종종 경험적 방법과 근사 알고리즘을 사용하여 해결된다.

개요

NP-완전 문제는 NP에 있으며, NP는 결정론적 튜링 기계에서 다항식 시간에 풀 수 있는 결정 문제의 집합으로 동등하게 정의될 수 있다.NP의 다른 모든 문제가 다항식 시간에 p로 변환(또는 축소)될 수 있는 경우 NP의 문제 p는 NP-완전입니다.

NP 의 모든 문제를 신속히 해결할 수 있을지는 불명확합니다.이것은 P 대 NP 문제라고 불립니다.그러나 NP-완전 문제를 신속하게 해결할 수 있다면, NP-완전 문제의 정의는 NP의 모든 문제를 모든 NP-완전 문제로 신속하게 환원할 수 있어야 한다고 명시되어 있기 때문에 NP-완전 문제를 신속하게 해결할 수 있습니다(즉, 다항식 시간 내에 줄일 수 있습니다).이 때문에, NP-완전 문제는 일반적으로 NP 문제보다 어렵거나 더 어렵다고 종종 말합니다.

형식적 정의

결정 문제 $(\$ C $)$ 는 $\scriptstyle C$ 다음과 같은 경우 NP-complete입니다.

$(\displaystyle$ \ $scriptstyle$ C $)$ 는 $\scriptstyle C$ NP입니다.
NP의 모든 문제는 다항식 시간에 ^[3]C $\$ C로 $\scriptstyle C$ 할 $\scriptstyle C$ 수 있습니다.

$\scriptstyle C$ $\$ C에 $\scriptstyle C$ 대한 $\scriptstyle C$ 솔루션이 다항식 시간에 검증 가능하다는 것을 입증함으로써 C $\$ C가 $\scriptstyle C$ NP에 있음을 나타낼 수 있다.

조건 2를 만족시키는 문제는 조건 ^[4]1을 만족하는지 여부에 관계없이 NP-hard라고 한다.

이 정의의 결과로 C $(\$ C $\scriptstyle C$ 에 대한 다항 시간 알고리즘(UTM 또는 기타 튜링 등가 추상 머신)이 있으면 NP의 모든 문제를 다항 시간 내에 해결할 수 있습니다.

배경

P, NP, NP-완전 및 NP-하드 문제에 대한 오일러 다이어그램입니다.왼쪽은 PnpNP라는 가정 하에 유효하고 오른쪽은 P=NP라는 가정 하에 유효하다. (빈 언어와 그 보완어가 NP-완전하지 않으며 일반적으로 P 또는 NP의 모든 문제가 NP-완전인 것은 아니다.)

NP-완전성의 개념은 1971년에 도입되었다(쿡-레빈 정리 참조). NP-완전이라는 용어는 나중에 도입되었다.1971년 STOC 컨퍼런스에서 컴퓨터 과학자 사이에 결정론적 튜링 기계에서 NP-완전 문제를 다항식 시간에 해결할 수 있는지에 대한 치열한 논쟁이 있었다.John Hopcroft는 NP-완전 문제가 다항 시간에 풀릴 수 있는지에 대한 문제는 나중에 풀어야 한다는 데 컨퍼런스의 모든 사람들에게 합의를 이끌어냈다. 왜냐하면 아무도 그들의 주장에 대한 공식적인 증거를 가지고 있지 않았기 때문이다.이것은 "P=NP인지에 대한 질문"으로 알려져 있다.

아무도 NP-완전 문제가 실제로 다항 시간에 풀 수 있는지 여부를 결정적으로 결정할 수 없었고, 이것은 수학의 가장 큰 미해결 문제 중 하나가 되었다.클레이 수학 연구소는 P=NP 또는 PnpNP라는 공식 증거를 가진 사람에게 미화 100만 달러의 현상금을 내걸고 있다.

NP-완전 문제의 존재는 명확하지 않다.쿡-레빈 정리는 부울 만족도 문제가 NP-완전이며, 따라서 그러한 문제가 존재함을 증명한다.1972년 리처드 카프는 다른 여러 문제들도 NP-완전 문제임을 증명했다(Karp의 21개 NP-완전 문제 참조). 따라서 NP-완전 문제(부울 만족도 문제 외에)의 종류가 있다.최초의 결과 이후, 수천 개의 다른 문제들이 NP-완전하다고 이전에 보여졌던 다른 문제들로부터의 감소에 의해 NP-완전성이라는 것이 증명되었다; 이러한 문제들 중 많은 것들이 개리와 존슨의 1979년 책인 컴퓨터와 난해성: NP-완전성 ^[5]이론 가이드에서 수집되었다.

NP-완전 문제

NP 완전성을 증명하기 위해 일반적으로 사용되는 감소를 나타내는 일부 NP 완전성 문제

새로운 문제가 NP-완전임을 증명하는 가장 쉬운 방법은 먼저 NP에 있음을 증명한 후 알려진 NP-완전 문제를 NP-완전 문제로 줄이는 것입니다.따라서 다양한 NP-완전 문제를 아는 것이 유용합니다.아래 목록에는 의사결정 문제로 표현될 경우 NP-완전인 잘 알려진 문제가 포함되어 있습니다.

오른쪽은 NP 완전성을 증명하기 위해 일반적으로 사용되는 문제와 감소에 대한 다이어그램입니다.이 그림에서는 문제가 아래에서 위로 감소합니다.이 다이어그램은 두 NP-완전 문제 사이에 다항 시간 감소가 존재하기 때문에 이러한 문제 간의 수학적 관계에 대한 설명으로 오해의 소지가 있습니다. 그러나 이 다항 시간 감소를 입증하는 것이 가장 쉬운 위치를 나타냅니다.

대부분의 경우 P의 문제와 NP-완전 문제 사이에는 약간의 차이만 있습니다.예를 들어, 부울 만족도 문제의 제한인 3-만족도 문제는 NP-완전인 반면, 약간 더 제한된 2-만족도 문제는 P(구체적으로는 NL-완전)에 있지만 약간 더 일반적인 최대 2-만족도 문제는 다시 NP-완전이다.그래프가 2가지 색상으로 색칠될 수 있는지 여부를 결정하는 것은 P에 있지만 3가지 색상으로 색칠할 수 있는지 여부는 평면 그래프로 제한하더라도 NP-완전입니다.그래프가 주기인지 초당인지 판단하는 것은 매우 간단하지만(L에서는), 최대 초당 또는 최대 주기 하위 그래프를 찾는 것은 NP-완전입니다.최적 솔루션의 고정 비율 이내에서의 배낭 문제의 해답은 다항식 시간으로 계산할 수 있지만, 최적의 해답을 찾는 것은 NP-완전입니다.

중간 문제

흥미로운 예는 그래프 동형성 문제, 즉 그래프 동형성이 두 그래프 사이에 존재하는지 여부를 결정하는 그래프 이론 문제입니다.정점의 이름을 바꾸는 것만으로 하나의 그래프를 다른 그래프로 변환할 수 있는 경우 두 그래프는 동형입니다.다음 두 가지 문제를 고려합니다.

그래프 동형:그래프₁ G는 그래프₂ G와 동형입니까?
서브그래프 동형:그래프₁ G는 그래프₂ G의 서브 그래프와 동형입니까?

Subgraph Isomorphism 문제는 NP-complete입니다.그래프 동형 문제는 NP에 있지만 P에도 NP-완전에도 없는 것으로 의심됩니다.이것은 어렵다고 생각되지만 NP-완전하다고 생각되지 않는 문제의 예입니다.이 클래스는 NP-Intermediate 문제라고 불리며 P exists NP일 경우에만 존재합니다.

NP-완전 문제 해결

현재 NP-완전 문제에 대해 알려진 모든 알고리즘은 입력 크기의 초다항식 시간을 필요로 하며, $k>0$ 는 일부 k $k>0$ > $0$ 에 대해 O $O(n^{k})$ $O(n^{k})$ k ) $O(n^{k})$ \ $displaystyle$ O ( $n$ ^ { $k$ ) } 에서의 $O(n^{k})$ ^[clarify] $k>0$ 지수적인 시간이 필요하며 더 빠른 알고리즘이 있는지 알 수 없다.

일반적으로 계산 문제를 해결하기 위해 다음과 같은 기술을 적용할 수 있으며, 이는 종종 훨씬 더 빠른 알고리즘을 발생시킵니다.

근사치:최적의 솔루션을 찾는 대신 최적의 솔루션과 최대 요인인 솔루션을 검색하십시오.
랜덤화:랜덤성을 사용하여 평균 실행 시간을 단축하고 알고리즘에 약간의 확률로 실패할 수 있도록 합니다.주의: 몬테카를로 방법은 유전 알고리즘과 같은 진화적 접근법이 있을 수 있지만, 이 특정한 의미에서 효율적인 알고리즘의 예는 아니다.
제약사항:입력의 구조(예: 평면 그래프)를 제한함으로써 일반적으로 더 빠른 알고리즘이 가능하다.
파라미터화: 입력의 특정 파라미터가 고정되어 있는 경우 고속 알고리즘이 있는 경우가 많습니다.
휴리스틱:대부분의 경우 '합리적으로 잘' 동작하지만 항상 빠르고 항상 좋은 결과를 얻을 수 있다는 증거는 없습니다.메타 휴리스틱 접근법이 자주 사용됩니다.

휴리스틱 알고리즘의 예로는 차선의 O(n log coloring n )\ $scriptstyle O(n\log$ n $)\$ gready $\scriptstyle O(n\log n)$ 컬러링 알고리즘이 있습니다.이것은 그래프 컬러링 글로벌레지스터 할당이라고 불리는 기법입니다.각 정점은 변수이고, 가장자리는 동시에 사용되는 변수 간에 그려지며, 색상은 각 변수에 할당된 레지스터를 나타냅니다.대부분의 RISC 머신에는 범용 레지스터가 상당히 많기 때문에 이 어플리케이션에는 휴리스틱접근법도 효과적입니다.

다양한 유형의 절감에 따른 완전성

위에서 주어진 NP-완전의 정의에서, 환원이라는 용어는 다항식 시간 다원 감소의 기술적 의미로 사용되었다.

또 다른 환원 유형은 다항식 시간 튜링 환원이다. $\scriptstyle X$ X $(\$ X $)$ 는 $\scriptstyle X$ 다항식 시간에 $\scriptstyle Y$ Y(\ $displaystyle \scriptstyle$ Y $)$ 를 $\scriptstyle Y$ $\scriptstyle Y$ $\scriptstyle Y$ 하는 서브루틴이 주어지면 이 서브루틴을 호출하여 $\scriptstyle X$ displaystyle \ $script style$ X)를 $\scriptstyle X$ 하는 프로그램을 작성할 수 있는 $\scriptstyle Y$ 에 대해 다항식 튜링할 수 있습니다 $.$ $\scriptstyle X$ 다항식 시간으로.이것은 프로그램이 서브루틴을 한 번만 호출할 수 있고 서브루틴의 반환값은 프로그램의 반환값이어야 하는 제약이 있는 다원 환원성과 대조됩니다.

만약 누군가가 다원적 감소 대신 튜링적 감소로 NP-완전으로의 유추를 정의한다면, 결과적인 문제 집합은 NP-완전보다 작지 않을 것이다; 그것이 더 커질지는 미해결 문제이다.

NP 완전성을 정의하기 위해 자주 사용되는 또 다른 감소 유형은 로그 공간 many-one 감소입니다. 이것은 로그 공간만으로 계산할 수 있는 다원 감소입니다.로그 공간에서 수행될 수 있는 모든 계산은 다항 시간 내에 수행될 수 있기 때문에 로그 공간 다항 시간 다항 시간 다항 시간 다항 시간 다항 시간 다항 시간 다항 시간 다항 시간 다항 시간 다항 시간 다항 시간 다항 시간 다항식 다항 시간 다항 시간 다항 시간 다항 시간 다항 시간 다항 시간 다항 시간 다항 시간 다항 감소가 있습니다.이러한 유형의 감소는 보다 일반적인 다항식-시간 다원 감소보다 더 정교하며, P-완전과 같은 더 많은 클래스를 구별할 수 있게 해준다.이러한 유형의 감소에서 NP-완전 변경의 정의는 여전히 해결되지 않은 문제입니다.현재 알려진 모든 NP-완전 문제는 로그 공간 감소 하에서 NP-완전입니다.현재 $AC_{0}$ $AC_{0}$ NP-완전 문제는 A C $AC_{0}$ 0(\ $display style$ AC_ ${0})$ 감소 $AC_{0}$ $NC_{0}$ N $NC_{0}$ (\ $display style$ NC_ ${0})$ 감소와 $NC_{0}$ $AC_{0}$ 훨씬 약한 감소에도 NP-완전 상태로 유지됩니다.SAT와 같은 일부 NP-Complete 문제는 다산술 시간 ^[6]투영 하에서도 완료된 것으로 알려져 있습니다.그러나 AC 감소는 다항식 시간 ^[7]감소보다 엄격하게 더 작은 클래스를 정의하는⁰ 것으로 알려져 있습니다.

명명

도널드 크누스에 따르면, "NP-complete"라는 이름은 알프레드 아호, 존 홉크로프트, 제프리 울먼이 유명한 교과서 "The Design and Analysis of Computer Algorithms"에서 널리 알렸다.그는 그가 이론 컴퓨터 ^[8]과학 커뮤니티에 대해 실시한 여론 조사 결과에 따라, 그들이 ("다항적으로-완전"에서) 책의 갤리 교정쇄의 변화를 도입했다고 보고합니다.여론조사에서^[9] 제기된 다른 제안으로는 "Herculean", "Fougable", "Steiglitz의 "hardboyed"와 "아마도 기하급수적인 시간"을 의미하는 Shen Lin의 약자 "PET"가 포함되었지만, P와 NP의 문제가 어느 방향으로 흘러가느냐에 따라 "지수의 시간" 또는 "이전 기하급수적인 시간"^[10]을 나타낼 수 있다.

일반적인 오해

다음과 같은 오해가 ^[11]자주 발생합니다.

"NP-완전 문제는 알려진 문제 중 가장 어려운 문제입니다.NP-완전 문제는 NP이기 때문에 실행 시간은 기껏해야 지수적입니다.그러나 Presburger 산술과 같은 일부 문제는 시간이 더 필요하다는 것이 입증되었습니다.일부 문제들 중, 정지 문제처럼 전혀 해결할 수 없다는 것이 입증되었습니다.
"NP-완전 문제는 매우 다양한 해결책이 있기 때문에 어렵습니다."한편, 솔루션 공간은 같은 크기이지만 다항식 시간(예를 들어 최소 스패닝 트리)에 걸쳐 해결할 수 있는 문제가 많이 있습니다.반면에, 무작위 다항식 시간 감소 하에서 NP-hard인 최대 하나의 해에는 NP-문제가 있다. (발리안트-바지라니 정리 참조)
"NP-완전 문제를 해결하려면 기하급수적인 시간이 필요합니다."첫째, 이것은 아직 풀리지 않은 질문인 P , NP를 의미할 것이다.또한, 일부 NP-완전 문제는 실제로 O(2n^√n)와 같은 초다항식으로 실행되지만 하위 지수 시간으로 실행되는 알고리즘을 가지고 있다.예를 들어 평면 그래프에 대한 독립 집합 및 지배 집합 문제는 NP-완전이지만 평면 분리기 ^[12]정리를 사용하여 지수 이하의 시간에 해결할 수 있다.
"NP-완전 문제의 각 사례는 어렵습니다."경우에 따라서는 일부 또는 대부분의 경우 다항식 시간 내에 쉽게 해결할 수 있습니다.그러나 P=NP가 아닌 한, 다항 시간 알고리즘은 특정 ^[13]크기의 기하급수적으로 많은 입력 중 다항식 이상에서 점근적으로 잘못되어야 합니다.
"P=NP이면 모든 암호는 깨질 수 있습니다."다항식의 차수나 상수가 충분히 클 경우 다항식 시간 문제는 실제로 해결하기 매우 어려울 수 있습니다.예를 들어 Advanced Encryption Standard와 같은 고정 키 길이를 가진 암호는 모든 키를 시도하면 일정 시간 내에 해독할 수 있습니다(따라서 이미 P로 알려져 있습니다). 그러나 현재 기술에서는 시간이 우주의 나이를 초과할 수 있습니다.또, 정보이론적인 시큐러티는, 무제한의 처리 능력에도 대응할 수 있는 암호화 방법을 제공합니다.

특성.

일부 고정 부호화에서는 결정 문제를 정식 언어로 볼 때 NP-완전 문제의 집합 NPC는 다음과 같이 닫히지 않습니다.

NPC=co-NP가 NP=co-NP인 경우에만 NPC가 보완 하에 닫혀 있는지 여부 및 NP=co-NP가 열린 ^[14]질문인지 여부는 알려지지 않았다.

「」를 참조해 주세요.

레퍼런스

인용문

^ 예를 들어, 각 변수에 true를 할당하는 것만으로 18번째 ${\overline {m}}\lor {\overline {r}}\lor {\overline {s}}$ m ${\overline {m}}\lor {\overline {r}}\lor {\overline {s}}$ r ${\overline {m}}\lor {\overline {r}}\lor {\overline {s}}$ s ${\overline {m}}\lor {\overline {r}}\lor {\overline {s}}$ display \ $display$ \ $overline$ { m } \ lor \ $overline$ { r } \ lor \ overline ${ s$ } ${\overline {m}}\lor {\overline {r}}\lor {\overline {s}}$ (및 완전한 공식)이 false가 됩니다.
^ Cobham, Alan (1965). "The intrinsic computational difficulty of functions". Proc. Logic, Methodology, and Philosophy of Science II. North Holland.
^ J. van Leeuwen (1998). Handbook of Theoretical Computer Science. Elsevier. p. 84. ISBN 978-0-262-72014-4.
^ J. van Leeuwen (1998). Handbook of Theoretical Computer Science. Elsevier. p. 80. ISBN 978-0-262-72014-4.
^ Garey, Michael R.; Johnson, D. S. (1979). Victor Klee (ed.). Computers and Intractability: A Guide to the Theory of NP-Completeness. A Series of Books in the Mathematical Sciences. San Francisco, Calif.: W. H. Freeman and Co. pp. x+338. ISBN 978-0-7167-1045-5. MR 0519066.
^ Agrawal, M.; Allender, E.; Rudich, Steven (1998). "Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem". Journal of Computer and System Sciences. 57 (2): 127–143. doi:10.1006/jcss.1998.1583. ISSN 1090-2724.
^ Agrawal, M.; Allender, E.; Impagliazzo, R.; Pitassi, T.; Rudich, Steven (2001). "Reducing the complexity of reductions". Computational Complexity. 10 (2): 117–138. doi:10.1007/s00037-001-8191-1. ISSN 1016-3328. S2CID 29017219.
^ Don Knuth, Tracy Larrabee 및 Paul M. Roberts, Wayback Machine 2010-08-27 Mathemical Writing Archived © 25, MAA No.14, 1989(Stanford Technical Report, 1987)
^ Knuth, D. F. (1974). "A terminological proposal". SIGACT News. 6 (1): 12–18. doi:10.1145/1811129.1811130. S2CID 45313676.
^ 폴링 또는 [1 ] 웨이백 머신에서 아카이브된 2011-06-07을 참조하십시오.
^ Ball, Philip. "DNA computer helps travelling salesman". doi:10.1038/news000113-10.
^ Bern(1990); De deneco, Klinz & Woorginger(2006);도른 등 (2005) harvts 오류: 대상 없음: Lipton & Tarjan(1980).
^ Hemaspaandra, L. A.; Williams, R. (2012). "SIGACT News Complexity Theory Column 76". ACM SIGACT News. 43 (4): 70. doi:10.1145/2421119.2421135. S2CID 13367514.
^ Talbot, John; Welsh, D. J. A. (2006), Complexity and Cryptography: An Introduction, Cambridge University Press, p. 57, ISBN 9780521617710, The question of whether NP and co-NP are equal is probably the second most important open problem in complexity theory, after the P versus NP question.

원천

Garey, M.R.; Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. ISBN 978-0-7167-1045-5. 이 책은 이론을 발전시키고 많은 NP-완전 문제를 정리하는 고전이다.
Cook, S.A. (1971). "The complexity of theorem proving procedures". Proceedings, Third Annual ACM Symposium on the Theory of Computing, ACM, New York. pp. 151–158. doi:10.1145/800157.805047.
Dunne, P.E. "An annotated list of selected NP-complete problems". COMP202, Dept. of Computer Science, University of Liverpool. Retrieved 2008-06-21.
Crescenzi, P.; Kann, V.; Halldórsson, M.; Karpinski, M.; Woeginger, G. "A compendium of NP optimization problems". KTH, Stockholm. Retrieved 2020-10-24.
Dahlke, K. "NP-complete problems". Math Reference Project. Retrieved 2008-06-21.
Karlsson, R. "Lecture 8: NP-complete problems" (PDF). Dept. of Computer Science, Lund University, Sweden. Archived from the original (PDF) on April 19, 2009. Retrieved 2008-06-21.
Sun, H.M. "The theory of NP-completeness". Information Security Laboratory, Dept. of Computer Science, National Tsing Hua University, Hsinchu City, Taiwan. Archived from the original (PPT) on 2009-09-02. Retrieved 2008-06-21.
Jiang, J.R. "The theory of NP-completeness" (PPT). Dept. of Computer Science and Information Engineering, National Central University, Jhongli City, Taiwan. Retrieved 2008-06-21.
Cormen, T.H.; Leiserson, C.E.; Rivest, R.L.; Stein, C. (2001). "Chapter 34: NP–Completeness". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 966–1021. ISBN 978-0-262-03293-3.
Sipser, M. (1997). "Sections 7.4–7.5 (NP-completeness, Additional NP-complete Problems)". Introduction to the Theory of Computation. PWS Publishing. pp. 248–271. ISBN 978-0-534-94728-6.
Papadimitriou, C. (1994). "Chapter 9 (NP-complete problems)". Computational Complexity (1st ed.). Addison Wesley. pp. 181–218. ISBN 978-0-201-53082-7.
게임과 퍼즐의 계산 복잡성
Tetris는 하드, 심지어 대략적인 수준까지
지뢰제거기는 NP완료!
를 클릭합니다Bern, Marshall (1990). "Faster exact algorithms for Steiner trees in planar networks". Networks. 20 (1): 109–120. doi:10.1002/net.3230200110..
를 클릭합니다Deĭneko, Vladimir G.; Klinz, Bettina; Woeginger, Gerhard J. (2006). "Exact algorithms for the Hamiltonian cycle problem in planar graphs". Operations Research Letters. 34 (3): 269–274. doi:10.1016/j.orl.2005.04.013..
를 클릭합니다Dorn, Frederic; Penninkx, Eelko; Bodlaender, Hans L.; Fomin, Fedor V. (2005). "Efficient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Branch Decompositions". Proc. 13th European Symposium on Algorithms (ESA '05). Lecture Notes in Computer Science. Vol. 3669. Springer-Verlag. pp. 95–106. doi:10.1007/11561071_11. ISBN 978-3-540-29118-3..
를 클릭합니다Lipton, Richard J.; Tarjan, Robert E. (1980). "Applications of a planar separator theorem". SIAM Journal on Computing. 9 (3): 615–627. doi:10.1137/0209046. S2CID 12961628..

추가 정보

Scott Aaronson, NP-complete Problems and Physical Reality, ACM SIGACT News, 제36권, 제1호(2005년 3월), 페이지 30-52.
랜스 포트노우, P 대 NP 문제 현황, 통신사 ACM, 제52권, 제9호(2009년), 페이지 78-86.

[1] 예를 들어, 각 변수에 true를 할당하는 것만으로 18번째 ${\overline {m}}\lor {\overline {r}}\lor {\overline {s}}$ m ${\overline {m}}\lor {\overline {r}}\lor {\overline {s}}$ r ${\overline {m}}\lor {\overline {r}}\lor {\overline {s}}$ s ${\overline {m}}\lor {\overline {r}}\lor {\overline {s}}$ display \ $display$ \ $overline$ { m } \ lor \ $overline$ { r } \ lor \ overline ${ s$ } ${\overline {m}}\lor {\overline {r}}\lor {\overline {s}}$ (및 완전한 공식)이 false가 됩니다.

[2] Cobham, Alan (1965). "The intrinsic computational difficulty of functions". Proc. Logic, Methodology, and Philosophy of Science II. North Holland.

[3] J. van Leeuwen (1998). Handbook of Theoretical Computer Science. Elsevier. p. 84. ISBN 978-0-262-72014-4.

[4] J. van Leeuwen (1998). Handbook of Theoretical Computer Science. Elsevier. p. 80. ISBN 978-0-262-72014-4.

[GareyJohnson-5] Garey, Michael R.; Johnson, D. S. (1979). Victor Klee (ed.). Computers and Intractability: A Guide to the Theory of NP-Completeness. A Series of Books in the Mathematical Sciences. San Francisco, Calif.: W. H. Freeman and Co. pp. x+338. ISBN 978-0-7167-1045-5. MR 0519066.

[6] Agrawal, M.; Allender, E.; Rudich, Steven (1998). "Reductions in Circuit Complexity: An Isomorphism Theorem and a Gap Theorem". Journal of Computer and System Sciences. 57 (2): 127–143. doi:10.1006/jcss.1998.1583. ISSN 1090-2724.

[7] Agrawal, M.; Allender, E.; Impagliazzo, R.; Pitassi, T.; Rudich, Steven (2001). "Reducing the complexity of reductions". Computational Complexity. 10 (2): 117–138. doi:10.1007/s00037-001-8191-1. ISSN 1016-3328. S2CID 29017219.

[8] Don Knuth, Tracy Larrabee 및 Paul M. Roberts, Wayback Machine 2010-08-27 Mathemical Writing Archived © 25, MAA No.14, 1989(Stanford Technical Report, 1987)

[9] Knuth, D. F. (1974). "A terminological proposal". SIGACT News. 6 (1): 12–18. doi:10.1145/1811129.1811130. S2CID 45313676.

[10] 폴링 또는 [1 ] 웨이백 머신에서 아카이브된 2011-06-07을 참조하십시오.

[11] Ball, Philip. "DNA computer helps travelling salesman". doi:10.1038/news000113-10.

[12] Bern(1990); De deneco, Klinz & Woorginger(2006);도른 등 (2005) harvts 오류: 대상 없음: Lipton & Tarjan(1980).

[13] Hemaspaandra, L. A.; Williams, R. (2012). "SIGACT News Complexity Theory Column 76". ACM SIGACT News. 43 (4): 70. doi:10.1145/2421119.2421135. S2CID 13367514.

[14] Talbot, John; Welsh, D. J. A. (2006), Complexity and Cryptography: An Introduction, Cambridge University Press, p. 57, ISBN 9780521617710, The question of whether NP and co-NP are equal is probably the second most important open problem in complexity theory, after the P versus NP question.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

v t 중요 복잡도 클래스(더 보기)
실현 가능하다고 생각되다	로그 타임 AC⁰ ACC⁰ TC⁰ L SL RL NL 엔씨 SC 참조 P P-완전 ZPP RP BPP BQP APX FP
실현 불가능한 것으로 생각됨	업. NP NP-완전 NP 하드 co-N co-NP-완전 오전 품질 관리 PH § P PP #P #P-완료 아이피 PSPACE PSPACE-완전
실현 불가능한 것으로 간주되다	제외 시간 넥스트 타임 엑스페이스 2회차 초등 홍보 R 재생 모든.
클래스 계층	다항식 계층 지수 계층 그르제고르치크 계층 산술적 계층 부울 계층
클래스 패밀리	DTime(DTIME) NTime(NTIME(NTIME) DSPACE 스페이스 확률적으로 확인할 수 있는 증거 인터랙티브 증명 시스템

Search

NP 완전성

네임스페이스

더

목차

개요

형식적 정의

배경

NP-완전 문제

중간 문제

NP-완전 문제 해결

다양한 유형의 절감에 따른 완전성

명명

일반적인 오해

특성.

「」를 참조해 주세요.

레퍼런스

인용문

원천

추가 정보

Search

NP 완전성

개요

형식적 정의

배경

NP-완전 문제

중간 문제

NP-완전 문제 해결

다양한 유형의 절감에 따른 완전성

명명

일반적인 오해

특성.

「 」를 참조해 주세요.

레퍼런스

인용문

원천

추가 정보

「」를 참조해 주세요.