는n를 나눕니다.

NP는 비 결정적 다항식 복잡도입니다. 비 결정적이라는 것이 무엇을 의미하는지 잘 모르겠습니다. 다항식 시간에 검증하는 것이 쉽다는 것을 의미한다고 생각합니다. 그러나 우리가 아직 알지 못했다면 처음부터 풀어야 할 다항식 시간 일 수도 있고 아닐 수도 있습니다. 대답. 다항식 시간에 풀 수 있을 수 있으므로 모든 P 문제도 NP 문제입니다. 정수 분해는 NP의 예로 인용되지만 개인적으로 P가 아닌 이유를 이해하지 못합니다. 시도 분해에는 O(sqrt(n)) 시간이 걸리기 때문입니다.

NP-Complete 전혀 이해가 안되지만 Traveling Salesman Problem이 이에 대한 예로 인용되었습니다.하지만 제 생각에 TSP 문제는 NP 일 수 있습니다. 경로가 미리 주어 졌는지 확인하려면 O(2n n2) time to solve, but O(n)와 같은 것이 필요하기 때문입니다.

NP-Hard는 꽉 찼다 고 가정합니다. 확인하기 어렵고 해결하기 어렵습니다.

댓글

• CS에 대한 질문을 읽었습니까? SE P, NP, NP-complete 및 NP-hard의 정의는 무엇입니까? ?
• ‘ 아직 링크를 보지 못했습니다. 아니요. ‘ 다시 읽어 보겠습니다. 감사합니다.
• CS.SE 답변은 상당히 경외심을 불러 일으 킵니다. ,하지만 ‘이 용어가 무엇을 의미하는지에 대해 매우 간결하고 오해의 소지가없는 설명을 거의 자세히 설명하지 않아도 가능하다고 생각합니다. @Nakano는 더 짧은 , ” 지점까지 답변 또는 CS.SE 게시물이 문제를 해결합니까?
• @MichaelT 해당 링크를 읽은 결과 정말 장황하고 몇 가지 사항이 명확하지 않다는 것을 알았습니다. 답보다 더 많은 질문을받은 것 같습니다.
• ” 비 결정적 “은 다음과 같이 해석 될 수 있습니다. ” 컴퓨터가 매번 올바른 선택을 선택하면 “.

답변

“

@Nakano : big-O 표기법에서 n는 입력 크기 (요소 수, 바이트, 자릿수 등)에 대한 척도이며 입력.

@Nakano 짧은 대답은 당신이 ‘ 괜찮다는 것입니다. 그래서 time co를 할 때 mplexity 분석 항상 n의 의미를 지정해야합니다 . n이 ” 입력 크기 “라는 주장은 우리가 일반적으로 n을 정의하는 방법에 대한 간결한 요약 일뿐입니다. Big-O 표기법이나 시간 복잡성에 대한 엄격한 정의의 일부가 ‘입니다. n이 입력의 값 일 때 정수 분해가 O (sqrt (n))라고 말하는 것이 맞다고 생각합니다. n이 크기를 의미하는 복잡성 결과는 일반적으로 n이 값을 의미하는 것보다 실제로 훨씬 더 유용합니다.

@Nakano It ‘ 또한 기술적으로 원시 연산 (덧셈, 곱셈, 메모리에서 읽기, 메모리에 쓰기, 두 숫자 비교)의 시간 복잡도를 정의해야합니다. 대부분의 경우 우리는 이러한 모든 프리미티브가 일정하다고 가정하거나 한 종류의 작업 만 계산합니다 (예 : 정렬 알고리즘의 경우 전통적으로 비교 계산). 정수 인수 분해 결과는 ‘이 모든 작업이 우리가 일반적으로하는 것처럼 일정한 시간이라고 가정하지 않습니다. 그렇지 않으면 숫자의 크기가 ‘별로 중요하지 않습니다.

답변

답변

길이 는 | w |로 작성되며 기호 수입니다.

예 : | hello | = 5 및 | ε | = 0. 모든 단어 w , | w | ∈ N 이므로 유한합니다.

Σ 는 알파벳이어야합니다. Σ ^＊ 집합에는 Σ ( ε 포함). Σ ⁺ 집합에는 Σ 이상의 모든 단어가 포함됩니다. i>, ε 제외. n ∈ N , Σ ⁿ 은 n 길이의 단어 집합입니다.

모든 알파벳 Σ , Σ ^＊ 및 Σ ⁺ 는 무한대입니다. 카운트 가능한 세트 .ASCII 문자 세트 Σ _ASCII 의 경우 정규 표현식 .* 및 .+는 Σ _ASCII ^＊ 및 Σ _ASCII ⁺

{0, 1} ⁷ 은 7 비트 ASCII 코드 {0000000, 0000001,…, 1111111}. {0, 1} ³² 는 32 비트 정수 값의 집합입니다.

Σ 는 알파벳이고 L 은 Σ ^＊ . L 은 Σ보다 언어 라고합니다. div> .

알파벳 Σ 의 경우 빈 집합 및 Σ ^＊ 는

. 전자는 종종 빈 언어 라고합니다. 빈 언어 {}와 빈 단어 { ε } 만 포함 된 언어가 다릅니다.

{

,1} ³² 는 유한 언어입니다.

언어는 무한한 수의 단어를 가질 수 있지만 모든 언어는 셀 수 있습니다. 10 진수 표기법의 정수를 나타내는 문자열 {1, 2,…}은 알파벳 {0, 1, 2, 3, 4, 5, 6, 7 , 8, 9}. 무한 문자열 세트 {2, 3, 5, 7, 11, 13,…}는 소수 표기법으로 소수를 나타내는 적절한 하위 집합입니다. 정규식 [+-]?\d+\.\d*([eE][+-]?\d+)?와 일치하는 모든 단어를 포함하는 언어는 ASCII 문자 집합에 대한 언어입니다 (C 프로그래밍 언어로 정의 된 유효한 부동 소수점 식의 하위 집합을 나타냄).

실수 집합은 셀 수 없기 때문에 모든 실수를 포함하는 언어는 없습니다 (어떤 표기법으로도).

Let Σ 는 알파벳이고 L ⊆ Σ ^＊ . 모든 입력에 대해 D 결정 L w ∈ Σ ^＊ 특성 함수 χ _L ( w ). 특성 함수는 다음과 같이 정의됩니다.

χL: Σ＊ → {0, 1} w ↦ 1, w ∈ L 0, otherwise.

이러한 기계를 결정자 iv id = “6ea6aaaecf라고합니다. L 의 경우 “> . “주어진 w , D 에 대해“ D ( w ) = x ”라고 씁니다. >은 x ”를 출력합니다.

많은 머신 모델이 있습니다. 오늘날 실제 사용되는 가장 일반적인 것은 튜링 머신 의 모델입니다. Turing 머신에는 셀에 클러스터 된 무제한 선형 저장소가 있습니다. 각 셀은 어느 시점에서든 정확히 하나의 알파벳 기호를 보유 할 수 있습니다. Turing 머신은 일련의 계산 단계로 계산을 수행합니다. 각 단계에서 하나의 셀을 읽고 해당 값을 덮어 쓸 수 있으며 읽기 / 쓰기 헤드를 왼쪽 또는 오른쪽 셀로 한 위치 이동합니다. 기계가 수행 할 작업은 유한 상태 자동 장치에 의해 제어됩니다.

유한 한 명령 세트와 무제한 저장 공간이있는 랜덤 액세스 기계는 Turing 기계 모델만큼 강력한 또 다른 기계 모델입니다.

p>

이 논의를 위해 우리는 우리가 사용하는 정확한 기계 모델에 신경 쓰지 않고 기계에 유한 결정 론적 제어 장치, 무제한 저장 공간이 있으며 일련의 단계로 계산을 수행한다고 말하기에 충분합니다. 계산할 수 있습니다.

귀하가 질문에 사용 했으므로 “이미 “big-O “표기법 여기에 간단한 복습 만 있습니다.

Let f : N →는 함수입니다.집합 O ( f )에는 모든 함수 g 가 포함됩니다. N → 상수 n ₀ ∈ N b이있는 div> N > 및 c ∈ N 모든 n ∈ N ( n > n ₀ 포함) g ( n ) ≤ c f ( n ).

이제 실제 질문에 접근 할 준비가되었습니다.

클래스 P 에는 L을 결정하는 튜링 머신 D 가있는 모든 언어 L 이 포함됩니다. 및 상수 k ∈ N (모든 입력 w , D 는 함수 T iv id = “ea6d47993e”에 대해 최대 T (| w |) 단계 후에 중지됩니다. > O ( n ↦ n ^k ).

O ( n ↦ n ^k ) 수학적으로 정확하지만 쓰기와 읽기가 불편합니다. 대부분의 사람들은 솔직히 말해서 저를 제외한 모든 사람 은 보통 간단하게 글을 씁니다. O ( n ^k ).

경계는 w . 따라서 소수의 언어에 대한 인수는 unaray 인코딩 의 숫자에 대해서만 정확합니다. 여기서 인코딩은 w 입니다. 숫자 n , 인코딩 길이 | w | n 에 비례합니다. 아무도 실제로 그러한 인코딩을 사용하지 않습니다. 가능한 모든 요소를 시도하는 것보다 더 고급 알고리즘을 사용하면 입력이 이진법 (또는 다른 염기)으로 인코딩 된 경우 소수의 언어가 P 에 남아 있음을 보여줄 수 있습니다. (많은 관심에도 불구하고 2004 년 수상 경력에 빛나는 논문에서 Manindra Agrawal, Neeraj Kayal 및 Nitin Saxena 에 의해서만 입증 될 수 있으므로 알고리즘은 그리 간단하지 않습니다.)

사소한 언어 {} 및 Σ ^＊ 및 중요하지 않은 언어 { ε }는 분명히 P (모든 알파벳 Σ ). 문자열을 입력으로 사용하고 문자열이 각 언어의 단어인지 여부를 알려주는 부울을 반환하는 함수를 선호하는 프로그래밍 언어로 작성하고 함수에 다항식 런타임 복잡성이 있음을 증명할 수 있습니까?

모든 일반 언어 (정규 표현식으로 설명되는 언어)는 P 입니다.

Σ 는 알파벳이고 L ⊆ Σ ^＊ . 두 단어 w , c ∈ 의 인코딩 된 튜플을 취하는 기계 V Σ ^＊ 및 유한 단계 수가 verifier for L 에 다음 속성이있는 경우

• 제공됨 ( w , c ), V 는 w ∈ L .
• w ∈ L 마다 c ∈ Σ ^＊ V ( w , c ) = 1

위 정의에서 c 를 증인 (또는 인증서 )이라고합니다. .

검증자는 w 가 실제로 L 에 있더라도 잘못된 증인에 대해 거짓 부정을 줄 수 있습니다. 그러나 오 탐지를 제공하는 것은 허용되지 않습니다. 또한 언어의 각 단어에 대해 최소한 한 명의 증인이 있어야합니다.

COMPOSITE 언어의 경우 소수가 아닌 모든 정수의 10 진수 인코딩을 포함합니다. , 증인은 인수 분해가 될 수 있습니다. 예를 들어 (659, 709)는 467231 ∈ COMPOSITE의 증인입니다. 증인이없는 상태에서 종이에 467231이 소수가 아님을 증명하는 것은 컴퓨터를 사용하지 않고는 어려울 것임을 쉽게 확인할 수 있습니다.

적절한 증인이 될 수있는 방법에 대해서는 아무 말도하지 않았습니다. 이것은 비 결정적 부분입니다.

NP 클래스에는 Turing 머신 이있는 모든 언어 L 이 포함됩니다. L 및 상수 k ∈ N 을 확인하는 V 입력 ( w , c ), V 는 최대 T (| w |) 함수의 단계 T ∈ O ( n ↦ n ^k ).

위의 정의는 각 w ∈ L 에 대해 증인 c 가 있음을 의미합니다. | c | ≤ T (| w |). (튜링 머신은 증인의 더 많은 기호를 볼 수 없습니다.)

NP 는 P 의 상위 집합입니다 (왜?). NP 에는 있지만 P 에는없는 언어가 있는지 여부는 알려져 있지 않습니다.

정수 분해는 그 자체로 언어가 아닙니다. 그러나 이와 관련된 결정 문제 를 나타내는 언어를 구성 할 수 있습니다. 즉, 모든 튜플 ( n , m )을 포함하는 언어는 n 이 인수 d 를 갖습니다. d ≤ m . 이 언어를 FACTOR라고합시다. FACTOR를 결정하는 알고리즘이있는 경우 각 소인수에 대해 재귀 이진 검색을 수행하여 다항식 오버 헤드만으로 전체 분해를 계산하는 데 사용할 수 있습니다.

FACTOR가 NP . 적절한 증인은 그 자체로 d 요소이며 검증자는 d ≤ m 및 n mod d = 0.이 모든 작업은 다항식 시간으로 수행 될 수 있습니다. (다시 말하지만, 인코딩 길이 가 중요하며 n 에서 로그 임을 기억하십시오.)

FACTOR도 P 에 있음을 보여줄 수 있다면 많은 멋진 상을받을 수 있습니다. (오늘날 암호화의 상당 부분을 깨뜨 렸습니다.)

NP 의 모든 언어에 대해 결정 em을 결정하는 무차별 대입 알고리즘이 있습니다. > 결정 론적으로. 모든 증인에 대해 철저한 검색을 수행합니다. (증인의 최대 길이는 다항식에 의해 제한됩니다.) 따라서 PRIMES를 결정하는 알고리즘은 실제로 COMPOSITE를 결정하는 무차별 대입 알고리즘이었습니다.

최종 질문을 해결하려면 축소 를 소개해야합니다. 축소는 이론적 컴퓨터 과학의 매우 강력한 개념입니다. 한 문제를 다른 문제로 줄이는 것은 기본적으로 다른 문제를 해결하여 한 문제를 해결하는 것을 의미합니다. 문제입니다.

Σ 는 알파벳이고 A 및 B 는 Σ 이상의 언어입니다. A 는 iv id = “916b322a57입니다. f 함수가있는 경우 “> 다항식 시간 다원 축소 가능 에서 B 로 : Σ ^＊ → Σ ^＊ .

• w ∈ A   ⇔   f ( w ) ∈ B   모든 w ∈ Σ ^＊ .
• f 함수는 모든 입력 에 대해 Turing 머신에서 계산할 수 있습니다. w | w |에서 다항식으로 묶인 여러 단계에서.

이 경우에는 A ≤ _p B .

예를 들어, A 는 삼각형을 포함하는 모든 그래프 (인접 행렬로 인코딩 됨)를 포함하는 언어라고합시다. (삼각형은 길이 3의주기입니다.) 더 나아가 B 는 0이 아닌 트레이스를 가진 모든 행렬을 포함하는 언어라고합시다. (행렬의 궤적은 주요 대각선 요소의 합입니다.) 그러면 A 는 B 로 줄일 수있는 다항식 다항식입니다. 이를 증명하려면 적절한 변환 함수 f 를 찾아야합니다. 이 경우 f 를 설정하여 인접 행렬의 3 ^rd 거듭 제곱을 계산할 수 있습니다. 이를 위해서는 각각 다항식 복잡성이있는 두 개의 행렬-행렬 곱이 필요합니다.

L ≤ _p L . (공식적으로 증명할 수 있습니까?)

이제 NP 에 적용하겠습니다.

L 언어는 NP -hard 입니다. i> L “≤ _p L 모든 언어 L “∈ NP .

NP 하드 언어 NP 자체 일 수도 있고 아닐 수도 있습니다.

언어 L 은 NP 입니다. -complete

• L ∈ NP 및
• L 은 NP -hard입니다.

가장 유명한 NP -완전한 언어는 SAT입니다. 만족할 수있는 모든 부울 공식을 포함합니다. 예 : ( a ∨ b ) ∧ (¬ a ∨ ¬ b ) ∈ SAT. 유효한 증인은 { a = 1, b = 0}입니다. 공식 ( a ∨ b ) ∧ (¬ a ∨ b ) ∧ ¬ b ∉ SAT. (어떻게 증명하겠습니까?)

SAT ∈ NP 를 보여주는 것은 어렵지 않습니다. SAT의 NP -경도를 보여주는 것은 약간의 작업이지만 1971 년 Stephen Cook 에 의해 수행되었습니다.

한 번 NP -완전한 언어가 알려졌을 때, 축소를 통해 다른 언어의 NP -완전성을 보여주는 것은 비교적 간단했습니다. 언어 A 가 NP -hard로 알려진 경우 A ≤ _p B 는 B 도 NP -단단함을 보여줍니다 (“ _p ”). 1972 년 Richard Karp 는 SAT의 (전 이적) 감소를 통해 NP -완전 함을 보여줄 수있는 21 개 언어 목록을 발표했습니다. (이 답변에서 실제로 읽어야 할 유일한 논문입니다. 다른 논문과 달리 이해하기 어렵지 않으며 축소를 통한 NP -완전성을 증명하는 방법에 대한 아주 좋은 아이디어를 제공합니다. )

마지막으로 짧은 요약입니다. NPH 및 NPC 기호를 사용하여 NP -hard 및 NP -완전 언어의 클래스를 나타냅니다.

• P ⊆ NP
• NPC ⊂ NP 및 NPC ⊂ NPH , 실제로 NPC = NP ∩ NPH 정의
• ( A ∈ NP ) ∧ ( B ∈ NPH )   ⇒   A ≤ _p B

NPC ⊂ NP 포함은 P = NP .이를 확인하려면 사소한 언어가 사소한 언어로 축소 될 수 없으며 P 에도 사소한 언어가 있음을 분명히하십시오. NP 의 중요하지 않은 언어로. s는 (그다지 흥미롭지 않은) 코너 케이스입니다.

부록

혼란의 주된 원인은“ n “의” O ( n ↦ f ( n )) 는 실제로 입력의 길이 를 참조 할 때 알고리즘 입력의 해석 입니다. 이것은 알고리즘의 점근 적 복잡성이 입력에 사용 된 인코딩 에 의존한다는 것을 의미하기 때문에 중요한 차이점입니다.

이번 주, 알려진 가장 큰

메르 센 프라임 을 달성했습니다. 현재 알려진 가장 큰 소수는 2 ^{74   207   281} − 1입니다.이 숫자는 너무 큽니다. 두통이 생기기 때문에 “다음 예에서 더 작은 것을 사용하겠습니다. 2 ³¹ – 1 = 2   147   483   647. 다른 방법으로 인코딩 할 수 있습니다.

• Mersenne 지수 (십진수)로 : 31 (2 바이트)
• 10 진수 : 2147483647 (10 바이트)
• 단항 number : 11111…11 여기서 …는 2   147

  483   640 개 이상 1 s (거의 2GiB)

이 모든 문자열은 동일한 숫자를 인코딩하며이 중 하나가 주어지면 동일한 숫자의 다른 인코딩을 쉽게 구성 할 수 있습니다. (10 진수 인코딩을 2 진수, 8 진수 또는 16 진수로 대체 할 수 있습니다. 당신이 원한다면 말. 상수 인자에 의해서만 길이를 변경합니다.)

소수성을 테스트하는 순진한 알고리즘은 단항 인코딩을위한 다항식 일뿐입니다. AKS 소수성 검정 은 십진수 (또는 기타 모든 기수 b ≥ 2 ). Lucas-Lehmer 소수성 테스트 는 Mersenne 소수 M _{p 에 p 가 홀수 소수이지만 Mersenne 지수 p 의 이진 인코딩 길이에서는 여전히 지수입니다 ( p 의 다항식). ).}

알고리즘의 복잡성에 대해 이야기하고 싶다면 우리가 어떤 표현을 사용하는지 매우 명확하게하는 것이 매우 중요합니다. 일반적으로 가장 효율적인 인코딩이 사용된다고 가정 할 수 있습니다. 즉, 정수의 바이너리입니다. (모든 소수가 메르 센 소수가 아니므로 메르 센 지수를 사용하는 것은 일반적인 인코딩 체계가 아닙니다.)

이론적 암호화에서 많은 알고리즘은 완전히 쓸모없는 k 1를 첫 번째 매개 변수로 사용합니다. 알고리즘은이 매개 변수를 보지 않지만 공식적으로 k 에서 다항식이 될 수 있습니다. 이는 보안 매개 변수 는 절차의 보안을 조정하는 데 사용됩니다.

바이너리 인코딩의 의사 결정 언어가 NP -완전한 일부 문제의 경우 의사 결정 언어가 더 이상 NP -포함 된 숫자의 인코딩이 단항으로 전환 된 경우 완료됩니다. 다른 문제에 대한 결정 언어는 NP -완전한 상태로 남아 있습니다. 후자는 강력하게 NP -완전 이라고합니다. 가장 잘 알려진 예는 빈 패킹 입니다.

방법을 보는 것도 흥미 롭습니다. 입력이 압축 되면 알고리즘의 복잡성이 변경됩니다. Mersenne 소수의 예에서 세 가지 인코딩을 보았습니다. 각 인코딩은 이전보다 대수적으로 더 압축되었습니다.

1983 년, Hana Galperin 및 Avi Wigderson 은 그래프의 입력 인코딩이 대수적으로 압축 될 때 일반적인 그래프 알고리즘의 복잡성에 대한 흥미로운 논문을 작성했습니다. 이러한 입력에 대해 위에서 삼각형을 포함하는 그래프의 언어 ( P 에서 명확하게 표시됨)는 갑자기 NP -완전이됩니다.

그리고 “는 P 및 NP 와 같은 언어 클래스가 문제 가 아닌 언어 에 대해 정의되기 때문입니다.

댓글

• 이 답변은 질문자를 이해하는 데 유용하지 않을 수 있습니다. 다른 답변을 읽고 Nanako가 어려움을 겪고있는 문제를 확인하세요. 답변이 도움이 될까요?
• 이 답변은 OP에는 도움이되지 않지만 다른 독자에게는 확실히 도움이됩니다 (자신 포함).
• 매우 유용한 답변! 수학 기호를 제대로 수정하지 않는 것이 좋습니다.

답변