계산 복잡성 이론을 설명합니다

https://stackoverflow.com/questions/308213

08-07-2019
|

문제

수학에 대한 배경을 가정하면 순진한 계산 복잡성 이론에 대한 일반적인 개요를 어떻게 제공 하시겠습니까?

P = NP 질문에 대한 설명을 찾고 있습니다. P 란? NP는 무엇입니까? NP- 하드 란 무엇입니까?

때때로 Wikipedia는 독자가 이미 관련된 모든 개념을 이미 이해하는 것처럼 쓰여집니다.

해결책

hoooo, 박사 학위 컴포지션 플래시백. 좋아, 여기 간다.

우리는 결정 문제에 대한 아이디어, 알고리즘이 항상 "예"또는 "아니오"에 대답 할 수있는 문제입니다. 또한 컴퓨터의 두 가지 모델 (실제로 튜링 머신)에 대한 아이디어가 필요합니다 : 결정 론적 및 비 결정적. 결정 론적 컴퓨터는 우리가 항상 생각하는 일반 컴퓨터입니다. 비 결정적 컴퓨터는 우리가 익숙해지는 것과 같은 컴퓨터입니다. 그 컴퓨터는 무제한 병렬성을 제외하고는 사용하는 것과 같습니다. Yogi Berra가 말했듯이, 길에서 포크에 올 때, 당신은 그것을 가져 가야합니다.

해당 답을 얻기 위해 알려진 다항식 시간 알고리즘이있는 경우 결정 문제는 P입니다. 결정 문제는 NP에 있습니다. 비 결정적 기계에 대한 알려진 다항식 시간 알고리즘이 답을 얻을 수있는 경우입니다.

P에있는 것으로 알려진 문제는 사소한 NP에서 --- 비 결정적 기계는 다른 프로세스를 포크하는 데 어려움을 겪지 않으며 결정 론적 과정처럼 행동합니다. P 또는 NP에서는 알려지지 않은 문제가 있습니다. 간단한 예는 길이 n의 모든 비트 벡터를 열거하는 것입니다. 어쨌든, 그것은 2가 필요합니다^N 단계.

(엄격히, 결정 문제는 NP에 있습니다. Nodeterministic 기계가 Poly-Time의 답변에 도달 할 수 있고 결정 론적 기계가 할 수 있다면 확인하다 솔루션은 폴리 시간에 맞습니다.)

그러나 폴리 타임 결정성 알고리즘이 알려지지 않은 NP에 알려진 몇 가지 문제가 있습니다. 다시 말해, 우리는 그들이 NP에 있다는 것을 알고 있지만 P에 있는지 알 수 없습니다. 모든 도시를 덮고 출발점으로 돌아가는 경로가 있습니까? 엑스 거리? 비 결정적 여행 세일즈맨이 도로에서 포크에 올 때마다, 그는 그것을 취하지 않았기 때문에 비 결정적 기계에서는 쉽습니다. 그의 클론은 방문하지 않은 다음 도시로 향하고 결국 메모를 비교하고 확인합니다. 클론 중 하나는 더 적은 수준을 취했습니다 엑스 거리.

(그런 다음, 기하 급수적으로 많은 클론이 어떤 클론을 죽여야하는지에 맞서 싸울 수 있습니다.)

의사 결정 TSP가 P에 있는지 여부는 알려져 있지 않습니다. 알려진 폴리 타임 솔루션은 알려져 있지 않지만 그러한 솔루션이 존재하지 않는 증거는 없습니다.

이제 한 가지 더 개념 : 결정 문제 P 및 Q가 주어지면 알고리즘이 p에 대한 솔루션을 다항식 시간에 Q에 대한 솔루션으로 변환 할 수 있다면 Q는 Q라고합니다. 폴리 타임 환원 가능 (또는 단지 환원 가능).

문제는 (1) NP에 있음을 증명할 수 있고 (2) 이미 NP- 완성으로 알려진 문제로 폴리 타임을 감소시킬 수 있음을 보여줄 수 있다면 NP- 완료입니다. (그 부분의 어려운 부분은 프로비였습니다 첫 번째 NP- 완료 문제의 예 : Steve Cook이 수행 한 것입니다. 쿡의 정리.)

그래서 실제로 말하는 것은 누군가가 하나의 NP- 완성 문제에 대한 폴리 타임 솔루션을 찾으면 자동으로 하나를 얻었습니다. 모두 NP- 완료 문제; 그것은 또한 p = np를 의미 할 것입니다.

문제는 NP-HARD 인 경우 NP- 완성 문제만큼 어려운 경우에만 NP-HARD입니다. 가장 짧은 경로를 찾는 데있어 더 기존의 여행 판매원 문제는 NP-HARD이며 엄격하게 NP- 완성이 아닙니다.

다른 팁

Michael Sipser'에스 계산 이론 소개 훌륭한 책이며 매우 읽을 수 있습니다. 또 다른 엄청난 자원은 Scott Aaronson입니다 이론적 컴퓨터 과학의 훌륭한 아이디어 강의.

사용되는 형식은 의사 결정 문제 (예/아니오 대답의 문제, 예를 들어 "이 그래프가 해밀턴주기를 갖는다")를 보는 것입니다. "언어" - 문자열 세트 - 대답이 예인 입력. "컴퓨터"가 무엇인지에 대한 공식적인 개념이 있으며, 해당 문제를 결정하기위한 다항식 시간 알고리즘이있는 경우 (입력 문자열이 주어 지거나, 예 또는 아니오라고 말하면) 문제는 P에 있습니다.

문제는 NP에 있습니다 확인 가능 다항식 시간에, 즉, 대답이 예인 입력의 경우, (다항식 크기) 인증서가있는 경우, 대답이 다항식 시간에 예라고 확인할 수 있습니다. [예 : 해밀턴주기를 인증서로 주었을 때, 당신은 그것이 하나인지 확인할 수 있습니다.

방법에 대해 아무 말도하지 않습니다 찾기 그 인증서. 분명히, 당신은 "가능한 모든 인증서"를 시도 할 수 있지만 지수 시간이 걸릴 수 있습니다. 당신이 항상 할 것인지는 확실하지 않습니다 가지다 예 또는 아니오를 결정하기 위해 다항식 시간 이상을 취하는 것; 이것은 P 대 NP 질문입니다.

문제는 해당 문제를 해결할 수 있다는 것이 NP의 모든 문제를 해결할 수 있다는 것을 의미합니다.

또한이 질문을 참조하십시오.컴퓨터 과학의 NP- 완성은 무엇입니까?

그러나 실제로,이 모든 것이 아마도 당신에게 단지 모호 할 것입니다. 예를 들어 Sipser의 책을 읽는 데 시간을 할애 할 가치가 있습니다. 아름다운 이론입니다.

이것은 Charlie의 게시물에 대한 의견입니다.

문제는 (1) NP에 있음을 증명할 수 있고 (2) 이미 NP- 완성으로 알려진 문제로 폴리 타임을 감소시킬 수 있음을 보여줄 수 있다면 NP- 완료입니다.

두 번째 조건에는 미묘한 오류가 있습니다. 실제로, 당신이 증명해야 할 것은 알려진 NP- 완료 문제 (예 : 와이)이 문제에 대한 다항식 시간 환원 가능 (문제라고 부르 자 엑스).

이러한 증거의 배후에 대한 추론은 NP-이 문제에 대한 문제를 해결하고 어떻게 든 폴리 타임 으로이 문제를 해결할 수있게되면, 당신은 또한 폴리 타임 솔루션을 찾는 데 성공했습니다. NP-눈에 띄는 문제는 눈에 띄지 않지만 (불가능하지는 않더라도) 오랜 스탠드를 해결하는 데 성공했을 것입니다. p = np 문제.

이 증거를 보는 또 다른 방법 y-> x, 그 다음에 ~ x-> ~ y. 다시 말해, 해결할 수 없다 와이 다항식 시간에는 불가능한 시간은 폴리 타임에서 X를 해결하지 않는 것을 의미합니다. 반면에, 폴리 타임으로 X를 해결할 수 있다면 폴리 타임에서 Y를 해결할 수 있습니다. 또한, 당신은 전달 성을 통해 폴리 타임에서 Y로 감소하는 모든 문제를 해결할 수 있습니다.

위의 설명이 충분히 분명하기를 바랍니다. 좋은 출처는 8 장입니다 알고리즘 설계 Kleinberg와 Tardos 또는 Cormen et al.

불행히도, 내가 알고있는 최고의 두 권의 책 (게이와 존슨 그리고 Hopcroft와 Ullman) 둘 다 대학원 증명 지향 수학 수준에서 시작합니다. 전체 문제가 오해하거나 오해하기가 매우 쉽기 때문에 이것은 거의 확실합니다. 제프 거의 귀를 씹었습니다 그가 너무 민속/jokey a tone에서 문제에 접근하려고 시도했을 때.

아마도 가장 좋은 방법은 단순히 Big-O 표기법으로 많은 실습 작업을하는 것입니다. 많은 예와 운동을 사용합니다. 또한보십시오 이 답변. 그러나 이것은 똑같은 것이 아니라는 점에 유의하십시오. 개별 알고리즘은 무증상으로 설명 할 수 있지만 문제 특정 복잡성은 진술입니다 가능한 모든 알고리즘 그것을 위해. 이것이 증거가 그렇게 복잡한 이유입니다!

나는 papadimitriou의 "계산 복잡성"을 기억합니다.

매우 단순화 : 문제는 가능한 모든 답변을 열거하고 각 답변을 확인하는 것인 경우 문제는 NP-Hard입니다.

주제에 대한 몇 가지 링크는 다음과 같습니다.

당신은 세트 카디널리티의 아이디어에 익숙합니다. 즉, 세트의 요소 수입니다. 그러면 NP는 미스터리 인 동안 정수 번호의 카디널리티를 나타내는 P와 같은 질문을 볼 수 있습니다. 모든 실수의 카디널리티?

내 단순화 된 대답은 다음과 같습니다. "계산 복잡성은 더 많은 요소를 추가 할 때 문제가 얼마나 어려워 지는지 분석하는 것입니다."

그 문장에서 "더 단단한"이라는 단어는 처리 시간이나 메모리 사용을 참조 할 수 있기 때문에 고의적으로 모호합니다.

컴퓨터 과학에서는 문제를 해결할 수있는 것으로 충분하지 않습니다. 합리적인 시간 안에 해결할 수 있어야합니다. 따라서 순수한 수학에서 당신은 방정식을 생각해냅니다. CS에서는 그 방정식을 개선하여 합리적인 시간에 문제를 해결할 수 있습니다.

그것이 내가 생각할 수있는 가장 간단한 방법입니다. 그것은 당신의 목적에 비해 너무 간단 할 수 있습니다.

당신이 얼마나 오래 있는지에 따라 DFA, NDFA에서 시작한 다음 동등하다는 것을 보여주는 것이 가장 좋을 것입니다. 그런 다음 그들은 ND 대 D를 이해하고 정규 표현을 좋은 부작용으로 훨씬 더 잘 이해할 것입니다.

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow