추치 튜링 논제에 따르면 모든 일관된 계산 모델과 튜링 기계는 다항식 시간 의미에서 동등하다. 우리는 일반적으로 다항식 시간을 알고리즘의 유효한 상징으로 사용하기 때문에, 이 주제는 튜링기에만 집중하고 다른 계산 모델은 무시할 수 있게 해준다. 마스터: 결정 문제
우리는 알고리즘 문제에 어떤 답이 필요한지 고려한다. 예를 들어, 검색 질문: 주어진 배열 A 와 숫자 S, 우리는 S 가 A (의사 결정 문제) 에 있는지 물어봐야 합니다. 또한 S 가 A 에 있다면 S 의 위치는 무엇입니까 (문제 검색). 또 다른 예는 완벽한 일치 문제입니다. 2 부도 G=(V, E) 가 주어지면, 2 부도의 각 노드가 정확히 모서리 세트의 한 가장자리에 속하도록 가장자리 세트 E 가 있는지 묻습니다 (의사 결정 문제). 더욱이, E 가 존재한다면, E 는 도대체 무엇입니까 (검색 문제).
당연히 우리는 일반적인 알고리즘 문제 A 에 대해, 우리는 모두 물어볼 수 있다. 첫째, 해답이 존재할까? 둘째, 솔루션이 있다면 무엇입니까? 이것은 A 의 의사 결정 문제와 A 의 검색 문제 (기능 문제라고도 함) 의 출처를 구분하는 직관적인 설명이다. 결정적인 질문에 대한 답은 "예" 또는 "아니오" 만 필요하지만, 구체적인 솔루션 형태 또는 "솔루션이 존재하지 않음" 은 검색 질문으로 돌아가야 합니다. 따라서 A 의 검색 문제에 대한 알고리즘은 당연히 A 의 의사 결정 문제에 대한 알고리즘입니다. 반대로, 주어진 A 의 의사 결정 문제에 대한 알고리즘, A 의 검색 문제에 대한 알고리즘이 있는지 여부, 계산성 이론과 계산복잡도 이론에 다른 답이 있다. 이는 계산복잡도 이론과 전신계산성 이론의 차이를 이해하는 기본적인 관찰이기도 하다.
계산성 이론에서는 의사 결정 문제와 검색 문제가 계산적 의미에서 동일하다고 해석할 수 있습니다 (의사 결정 문제 참조). 계산 복잡도에서 Khuller 와 Vazirani 는 1990 의 P≠NP 의 가설에서 계획 4- 음영 문제에 대한 의사 결정 문제가 P 에 있음을 증명했으며, 첫 번째 사전 순서가 있는 음영을 찾기가 어렵습니다.
따라서 계산성 이론에서 결정적인 문제에만 집중하는 것은 합리적이다. 계산 복잡성 이론에서 의사 결정 문제는 P, n P, PSPACE 와 같은 몇 가지 기본 복잡성 클래스와 P 와 NP 의 관계와 같은 몇 가지 기본 문제를 정의하지만 FP, FNP 등과 같은 함수 문제 복잡성 클래스도 정의합니다. ) 및 TFNP 와 같은 특수한 함수 문제의 복잡성 클래스도 점차 주목을 받고 있습니다. 위에서 설명한 계산 복잡성 이론의 연구 대상은 계산 작업을 수행하는 데 사용되는 자원입니다. 특히 시간과 공간은 가장 중요한 두 가지 자원이다.
우리는 시간을 예로 들어 알고리즘 분석의 기초를 토론했다. 입력 길이 (n 으로 설정) 를 변수로 사용하는 경우, 한 알고리즘이 다른 계산 모델에서 구현될 때 상수 계수가 다를 수 있으므로 (계산 가능성 이론 참조) T(n) 를 큰 O 표현식으로 표시하므로 다른 계산 모델에서 구현되는 상수 계수를 무시할 수 있습니다.
검색한 계산 작업을 예로 들어 보겠습니다. 검색 문제에서 특정 숫자 S 와 길이가 N 인 배열 A (배열 내 위치는 1 에서 N 으로 표시됨) 를 지정하면 A 에서 S 의 위치를 찾을 수 있습니다. A 에 없을 때 찾지 못했다고 보고합니다. 이때 길이를 n+ 1 으로 입력합니다. 다음 절차는 가장 간단한 알고리즘입니다. A 의 각 숫자를 차례로 스캔하여 S 와 비교하고, 같으면 현재 위치를 반환합니다. 우리가 모든 숫자를 스캔해도 알고리즘이 멈추지 않고 not found 로 돌아옵니다.
A 의 모든 위치에서 s 가 똑같이 가능하다고 가정하면 알고리즘에는1/n (1+2+...+n) = n (n+ 1 이 필요합니다 큰 O 표현식에 대한 지식에서 우리는 알고리즘에 필요한 시간이 O(n) 라는 것을 알고 있다.
그리고 만약 우리가 더 이상 A 가 정렬되어 있다고 가정한다면, 우리는 이분법 알고리즘을 가지고 있다. 이렇게 하면 알고리즘의 운행 시간은 O(logn) 이다. (알버트 아인슈타인, Northern Exposure (미국 TV 드라마), 도전명언) 계산 작업을 수행할 때 알고리즘에 따라 실행 시간이 크게 다르다는 것을 알 수 있습니다. 계산 문제를 서로 다른 계산 모델에 필요한 자원에 따라 분류하여 알고리즘 문제' 난이도' 의 범주를 얻습니다. 이것이 복잡성 이론에서 복잡성 클래스 개념의 원천입니다. 예를 들어, 결정 론적 튜링 머신에서 문제를 해결하는 데 걸리는 시간이 결정 다항식 (입력 길이는 다항식의 불확정 요소) 을 초과하지 않는 경우 이러한 문제의 집합을 P (다항식 시간 튜링 기계) 라고 부릅니다. 위의 정의에서 "결정적 튜링 기계" 를 "불확실성 튜링 기계" 로 변경하면 결과 문제 세트는 NP (불확실성 다항식 시간 튜링 기계) 입니다. 마찬가지로 N 을 입력 길이로 설정하면 "확실성 튜링기에서 필요한 공간이 O(logn) 를 초과하지 않는 알고리즘 문제 세트" (L) "깊이는 O(logn), 입력도 (팬 인) 는 O (/KLOC-;
복잡한 문제를 정의하는 목적은 모든 알고리즘 문제를 분류하여 현재 알고리즘의 난이도와 가능한 발전 방향을 결정하는 것입니다. 이것은 복잡성 이론의 주선이다: 추상화와 분류 알고리즘 문제. 예를 들어, 큰 O 표현식을 사용하면 서로 다른 계산 모형에 도입된 상수 요소를 무시할 수 있습니다. 두 번째 중요한 이론적 가정은 다항식 시간이 알고리즘의 유효한 플래그 (지수 시간에 해당) 라고 가정합니다. 이렇게 하면 복잡도 클래스를 통해 다항식 차수의 차이를 무시하고 다항식 시간과 지수 시간의 차이에 집중할 수 있습니다. (다항식 시간은 논란의 여지가 있는 효과적인 알고리즘의 상징이다. 예를 들어, 알고리즘의 실행 시간은 N 이고, 느리다고 생각할 수도 있다. 이론과 실천을 보다. ) 이 문서의 나머지 부분에서 "효과적인 알고리즘" 의 요약은 "다항식 알고리즘" 과 동등하며, 여러 알고리즘 문제를 연결하는 주요 기술적 수단으로, 알고리즘 문제의 상대적 난이도를 어느 정도 정의합니다. 간단히 말해서, 우리가 알고리즘 임무 A 와 B 를 가지고 있다고 가정해 봅시다. "A 가 B 보다 간단하다" (A≤B 로 표시) 는 무엇을 의미합니까? 요약의 관점에서 볼 때, 즉, B 에 대한 유효한 알고리즘 M 이 있다면, M 을 참조할 수 있는 유효한 알고리즘 N 이 있고, 결국 A 문제를 해결할 수 있습니다. (존 F. 케네디, Northern Exposure (미국 TV 드라마), 성공명언)
정점 커버 문제와 독립 세트 문제를 예로 들어 설명하겠습니다. 이 두 가지 문제는 모두 그래프 이론의 문제이다. 무향 그래프 G=(V, E) 와 자연수 K 가 주어지면 점 세트 커버 문제는 V 의 하위 집합 S 를 구하는 것입니다. E ∩ e 및 s ∩ s, s ∩ e 및 | s | ≤ k; 독립집합 문제도 V 의 하위 집합 S 를 구하는 것입니다. 요구 사항은 무엇입니까? S 1, S2 ∩ s, (s 1, S2)? E 그리고 | s |S|≤k k K.
간단한 관찰은 G=(V, E), S? V 는 S 가 G 의 패치에서 개별 점 세트인 경우에만 점 세트를 덮는 것입니다 (세트 크기 유지). 이 관찰을 사용 하 여, 우리는 커버 포인트 세트 문제를 해결 하기 위해 알고리즘 M 을 가정, 우리는 다음과 같이 독립적인 점 세트를 해결 하기 위해 알고리즘 N 을 설계 했습니다:
알고리즘 n. 입력: 주어진 무향 그래프 G=(V, e), 자연수 k; 출력: 크기 ≤ k 의 독립 점 세트 (있는 경우, 그렇지 않은 경우 "없음" 반환); 알려진 입력은 (무향도 G, 자연수 K) 인 알고리즘 M 이 ≤ k 크기의 커버 세트를 출력합니다 (있는 경우). 그렇지 않으면 "없음" 을 반환합니다. 알고리즘 단계: g 의 경우 g 의 보충 그래프 g' 를 생성합니다. M 을 호출하고 (g', k) 로 입력합니다. M 이 "없음" 을 반환하면 출력이 존재하지 않습니다. M 이 S 로 돌아간다면? V, 출력 S. 보완 그래프를 생성하는 단계가 유효하면 M 이 유효하면 N 도 유효하다는 것을 알 수 있습니다. 일반적으로 B 에 유효한 알고리즘 M 이 있고 B 를 Oracle 로 사용하여 A 문제를 해결하는 알고리즘 N 이 있는 경우 N 이 유효하면 A 문제를 해결하는 효과적인 알고리즘 N' 이 있습니다. N 에서 B 를 쿼리하는 대신 특정 M 알고리즘만 사용하면 됩니다. 이 특성의 기본 해석은 한 다항식의 불확정 요소가 다른 다항식으로 대체되면 여전히 다항식이라는 것입니다.
따라서 약속의 관점에서 볼 때, 다음과 같은 표현은 "A 가 B 보다 간단하다" (A≤B 로 표시) 와 같다고 볼 수 있습니다.
A 를 b 로 낮추거나 a 를 b 로 낮추거나 a 를 b 로 낮출 수 있습니다. B 의 문제를 제기하고 A 를 해결하는 알고리즘이 있습니다. B 의 문제를 질의하여 A 의 문제를 해결합니다.