계산 복잡도 이론

이론 컴퓨터 과학에서, 계산 복잡도 이론은 계산 문제를 자원 사용에 따라 분류하고, 이 클래스들을 서로 관련짓는 데 초점을 맞춘다.계산 문제는 컴퓨터가 해결하는 작업이다.계산 문제는 알고리즘과 같은 수학적 단계를 기계적으로 적용함으로써 해결할 수 있다.

알고리즘이 무엇을 사용하든, 그 솔루션에 상당한 리소스가 필요한 경우, 문제는 본질적으로 어려운 것으로 간주됩니다.이 이론은 이러한 문제를 연구하기 위해 수학적인 계산 모델을 도입하고 계산 복잡성, 즉 시간과 저장과 같은 문제를 해결하기 위해 필요한 자원의 양을 수량화함으로써 이러한 직관을 공식화한다.통신량(통신 복잡도에 사용), 회선 내 게이트 수(회선 복잡도에 사용), 프로세서 수(병렬 컴퓨팅에 사용)와 같은 다른 복잡도 척도도 사용됩니다.계산 복잡도 이론의 역할 중 하나는 컴퓨터가 할 수 있는 것과 할 수 없는 것에 대한 실질적인 한계를 결정하는 것입니다.P 대 NP 문제는 7가지 밀레니엄 상 문제 중 하나이며 ^[1]계산 복잡성 분야에 전념하고 있습니다.

이론 컴퓨터 공학에서 밀접하게 관련된 분야는 알고리즘과 계산 가능성 이론의 분석입니다.알고리즘의 분석과 계산 복잡도 이론의 주요 차이점은 전자는 문제를 해결하기 위해 특정 알고리즘이 필요로 하는 자원의 양을 분석하는데 전념하는 반면 후자는 동일한 문제를 해결하기 위해 사용될 수 있는 모든 가능한 알고리즘에 대해 보다 일반적인 질문을 한다는 것이다.좀 더 정확하게는 계산 복잡도 이론은 적절하게 제한된 자원으로 해결할 수 있거나 해결할 수 없는 문제를 분류하려고 한다.결과적으로, 이용 가능한 자원에 제한을 가하는 것은 계산의 복잡성과 계산가능성 이론을 구별하는 것이다: 후자 이론은 원칙적으로 어떤 종류의 문제를 알고리즘적으로 해결할 수 있는지를 묻는다.

계산상의 문제

문제 인스턴스

계산 문제는 모든 인스턴스에 대한 일련의 솔루션(아마도 빈)과 함께 인스턴스의 무한 집합으로 볼 수 있습니다.계산 문제의 입력 문자열을 문제 인스턴스라고 하며 문제 자체와 혼동해서는 안 됩니다.계산 복잡도 이론에서, 문제는 풀어야 할 추상적인 질문을 말한다.이와는 대조적으로, 이 문제의 예는 결정 문제에 대한 입력으로 작용할 수 있는 다소 구체적인 발언이다.예를 들어 primity test의 문제를 생각해 보겠습니다.인스턴스는 숫자(예: 15)이며, 그 숫자가 소수일 경우 해결책은 "yes"이고, 그렇지 않을 경우 "no"입니다(이 경우 15는 소수가 아니며 대답은 "no"입니다).즉, 인스턴스는 문제에 대한 특정 입력이며 해결책은 주어진 입력에 대응하는 출력입니다.

문제와 사례의 차이를 더욱 강조하기 위해 출장 중인 세일즈맨 문제의 의사결정 버전의 다음 사례를 검토합니다.독일의 15대 도시를 모두 통과하는 최대 2000km의 경로가 있습니까?이 특정 문제에 대한 정량적 답변은 총 길이가 최대 10km인 밀라노의 모든 사이트를 왕복하는 등 문제의 다른 사례를 해결하는 데 거의 도움이 되지 않습니다.이러한 이유로 복잡성 이론은 특정 문제가 아닌 계산 문제를 다룬다.

문제 인스턴스 표시

계산상의 문제를 고려할 때 문제 인스턴스는 알파벳 위에 있는 문자열입니다.보통 알파벳은 이진 알파벳(즉, 집합 {0,1})으로 간주되므로 문자열은 비트스트링입니다.실제 컴퓨터와 마찬가지로 비트스트링 이외의 수학적 오브젝트는 적절히 부호화되어야 합니다.예를 들어 정수는 바이너리 표기로 나타내며 그래프는 인접 매트릭스를 통해 직접 부호화하거나 인접 목록을 바이너리로 부호화할 수 있습니다.

복잡성 이론의 일부 증명은 입력 부호화의 구체적인 선택을 정기적으로 가정하지만, 논의는 부호화의 선택으로부터 독립할 수 있을 만큼 추상적으로 유지하려고 한다.이는 서로 다른 표현을 서로 효율적으로 변환함으로써 달성할 수 있습니다.

정식 언어로서의 의사결정 문제

의사결정 문제는 계산 복잡성 이론의 핵심 연구 대상 중 하나이다.결정문제는 특수한 유형의 계산문제로 답이 예 또는 아니오이거나 번갈아 1 또는 0 중 하나입니다.결정문제는 형식언어로 볼 수 있습니다.여기서 언어의 구성원은 출력이 yes인 인스턴스이고 비구성원은 출력이 no인 인스턴스입니다.알고리즘의 도움을 받아 주어진 입력 문자열이 고려 중인 정식 언어의 구성원인지 여부를 결정하는 것이 목적입니다.이 문제를 결정하는 알고리즘이 yes라고 응답하면 알고리즘은 입력 문자열을 받아들인다고 합니다.그렇지 않으면 입력을 거부한다고 합니다.

의사결정 문제의 예는 다음과 같습니다.입력은 임의 그래프입니다.문제는 주어진 그래프가 연결되어 있는지 여부를 결정하는 것입니다.이 결정 문제와 관련된 공식 언어는 연결된 모든 그래프의 집합입니다. 이 언어의 정확한 정의를 얻으려면 그래프를 이진 문자열로 인코딩하는 방법을 결정해야 합니다.

기능상의 문제

함수 문제는 모든 입력에 대해 (전체 함수의) 단일 출력이 예상되지만, 출력은 결정 문제보다 더 복잡합니다. 즉, 출력이 예 또는 아니오일 뿐만이 아닙니다.주목할 만한 예로는 출장 세일즈맨 문제와 정수 인수분해 문제가 있습니다.

기능 문제의 개념이 의사결정 문제의 개념보다 훨씬 풍부하다고 생각하는 것은 유혹적입니다.다만, 실제로는 그렇지 않습니다.기능의 문제가 의사결정 문제로 재연될 수 있기 때문입니다.예를 들어, 두 정수의 곱셈은 a × b = c가 유지되도록 3배(a, b, c)의 집합으로 표현될 수 있다.주어진 트리플이 이 집합의 멤버인지 아닌지를 결정하는 것은 두 숫자를 곱하는 문제를 해결하는 것입니다.

인스턴스 크기 측정

계산 문제 해결의 난이도를 측정하기 위해 최적의 알고리즘이 문제를 해결하는 데 얼마나 많은 시간이 필요한지 알고 싶을 수 있습니다.그러나 일반적으로 실행 시간은 인스턴스에 따라 다를 수 있습니다.특히 인스턴스가 클수록 해결하는 데 더 많은 시간이 필요합니다.따라서 문제 해결에 필요한 시간(또는 필요한 공간 또는 복잡성의 측정)은 인스턴스 크기의 함수로 계산됩니다.이것은 보통 비트 단위의 입력 크기로 간주됩니다.복잡성 이론은 입력 크기의 증가에 따라 알고리즘이 어떻게 확장되는지에 관심이 있습니다.예를 들어, 그래프가 연결되어 있는지 여부를 찾는 문제에서, 2n개의 정점이 있는 그래프의 문제를 푸는 데 걸리는 시간과 비교해 얼마나 더 많은 시간이 걸립니까?

입력 사이즈가 n이면 소요시간은 n의 함수로 나타낼 수 있다.같은 크기의 다른 입력에 걸리는 시간은 다를 수 있기 때문에 최악의 경우 시간 복잡도 T(n)는 크기 n의 모든 입력에 걸리는 최대 시간으로 정의된다.T(n)가 n의 다항식일 경우 알고리즘은 다항식 시간 알고리즘이라고 한다.코밤의 논문은 다항 시간 알고리즘을 허용한다면 실현 가능한 양의 자원으로 문제를 해결할 수 있다고 주장한다.

기계 모델 및 복잡성 측정

튜링 기계

튜링 기계는 일반적인 계산 기계의 수학적 모델이다.테이프 조각에 포함된 기호를 조작하는 이론적 장치입니다.튜링 머신은 실용적인 컴퓨팅 테크놀로지가 아니라 컴퓨팅 머신의 일반적인 모델입니다.고급 슈퍼컴퓨터부터 연필과 종이를 가진 수학자까지 모든 것을 말합니다.알고리즘으로 문제를 풀 수 있다면, 그 문제를 푸는 튜링 기계가 존재한다고 믿어진다.실제로, 이것은 처치-튜링 논문의 진술이다.게다가, 오늘날 우리에게 알려진 RAM 기계, Conway's Game of Life, 셀룰러 오토마타, 람다 미적분 또는 어떤 프로그래밍 언어 같은 다른 계산 모델에서 계산될 수 있는 모든 것은 튜링 기계에서 계산될 수 있는 것으로 알려져 있다.튜링 기계는 수학적으로 분석하기 쉽고, 다른 계산 모델만큼 강력하다고 여겨지기 때문에, 튜링 기계는 복잡도 이론에서 가장 일반적으로 사용되는 모델이다.

결정론적 튜링 기계, 확률론적 튜링 기계, 비결정론적 튜링 기계, 양자 튜링 기계, 대칭 튜링 기계 및 교대 튜링 기계와 같은 많은 유형의 튜링 기계가 복잡도 클래스를 정의하는데 사용된다.이들은 모두 원칙적으로 동등하게 강력하지만, 자원(시간이나 공간 등)이 한정되어 있는 경우에는 이들 중 일부는 다른 것보다 더 강력할 수 있습니다.

결정론적 튜링 기계는 미래의 행동을 결정하기 위해 고정된 규칙 집합을 사용하는 가장 기본적인 튜링 기계이다.확률론적 튜링 기계는 랜덤 비트의 추가 공급을 가진 결정론적 튜링 기계이다.확률론적 결정을 내리는 능력은 알고리즘이 문제를 보다 효율적으로 해결하는 데 종종 도움이 된다.랜덤 비트를 사용하는 알고리즘을 랜덤화 알고리즘이라고 부릅니다.비결정론적 튜링 기계는 결정론적 튜링 기계로, 주어진 상태에서 튜링 기계가 여러 가지 가능한 미래 동작을 가질 수 있도록 하는 비결정론의 추가 특징을 가지고 있다.비결정론을 보는 한 가지 방법은 튜링 기계가 각 단계에서 많은 가능한 계산 경로로 분기하는 것이며, 만약 그것이 이 분기들 중 어느 한 가지에서 문제를 해결한다면, 그것은 문제를 해결했다고 한다.분명히 이 모델은 물리적으로 실현 가능한 모델이 아니라 이론적으로 흥미로운 복잡성 클래스를 발생시키는 흥미로운 추상 기계입니다.예에 대해서는 비결정론적 알고리즘을 참조하십시오.

기타 기계 모델

표준 멀티 테이프 튜링 기계와 다른 많은 기계 모델들이 문헌에서 제안되어 왔다. 예를 들어 랜덤 액세스 기계들이다.아마도 놀랍게도, 이러한 모델들은 별도의 계산 능력을 제공하지 않고도 다른 모델로 변환할 수 있습니다.이러한 대체 모델의 시간 및 메모리 소비량은 ^[2]다를 수 있습니다.이 모든 모델의 공통점은 기계가 결정적으로 작동한다는 것입니다.

그러나 일부 계산 문제는 더 특이한 리소스 측면에서 분석하기가 더 쉽습니다.예를 들어, 비결정론적 튜링 기계는 동시에 많은 다른 가능성을 확인하기 위해 분기할 수 있는 계산 모델이다.비결정론적 튜링 기계는 우리가 물리적으로 알고리즘을 계산하기를 원하는 방법과는 거의 관련이 없지만, 그것의 분기는 우리가 분석하고자 하는 많은 수학적 모델을 정확히 포착한다. 그래서 비결정론적 시간은 계산 문제를 분석하는데 매우 중요한 자원이다.

복잡도 측정

주어진 시간과 공간을 사용하여 문제를 해결하는 것이 무엇을 의미하는지에 대한 정확한 정의를 위해 결정론적 튜링 기계와 같은 계산 모델이 사용된다.입력 x에 대한 결정론적 튜링 기계 M에 의해 요구되는 시간은 기계가 멈추고 답을 출력하기 전에 이루어지는 총 상태 전환 또는 단계 수("예" 또는 "아니오")입니다.튜링 머신 M은 길이 n의 각 입력에 대해 M이 필요로 하는 시간이 f(n) 이상이면 시간 f(n) 내에서 동작한다고 한다.판정 문제 A는 시간 f(n)에 동작하는 튜링 기계가 있으면 시간 f(n)에 풀 수 있다.복잡도 이론은 문제를 난이도에 따라 분류하는 데 관심이 있기 때문에, 어떤 기준에 따라 일련의 문제를 정의한다.예를 들어 결정론적 튜링 기계 상에서 시간 f(n) 내에 해결 가능한 문제 세트는 DTIME(f(n)로 나타난다.

공간 요건에 대해서도 유사한 정의를 내릴 수 있습니다.시간과 공간은 가장 잘 알려진 복잡성 리소스이지만, 모든 복잡성 척도는 계산 리소스로 볼 수 있습니다.복잡도 측정은 매우 일반적으로 Blum 복잡도 공리에 의해 정의된다.복잡도 이론에서 사용되는 다른 복잡도 측정에는 통신 복잡도, 회선 복잡도 및 의사결정 트리의 복잡도가 포함됩니다.

알고리즘의 복잡도는 종종 빅 O 표기법을 사용하여 표현됩니다.

최적의 경우, 최악의 경우 및 평균적인 경우의 복잡성

최선의 경우, 최악의 경우 및 평균적인 경우 복잡도는 동일한 크기의 서로 다른 입력의 시간 복잡도(또는 기타 복잡도 측정)를 측정하는 세 가지 다른 방법을 말합니다.크기가 n인 일부 입력은 다른 입력보다 해결 속도가 빠를 수 있으므로 다음과 같은 복잡성을 정의합니다.

1. 베스트 케이스의 복잡성:이것이 크기 n을 최적으로 입력하기 위한 문제 해결의 복잡성입니다.
2. 평균 케이스의 복잡성:이것은 평균적으로 문제를 해결하는 것의 복잡성입니다.이 복잡성은 입력에 대한 확률 분포와 관련하여만 정의됩니다.예를 들어, 같은 크기의 모든 입력이 동등하게 나타날 가능성이 있다고 가정할 경우, 평균 사례 복잡도는 크기 n의 모든 입력에 대해 균일한 분포에 대해 정의할 수 있다.
3. 상각분석:상각 분석은 알고리즘의 전체 연산에 걸쳐 비용이 많이 드는 연산과 비용이 적게 드는 연산을 모두 고려합니다.
4. 최악의 경우 복잡성:이것은 크기 n의 최악의 입력에 대한 문제를 해결하기 위한 복잡성입니다.

값싼 것부터 비싼 것까지의 순서는 Best, average(이산 균등 분포의 경우), 상각, worst입니다.

예를 들어 결정론적 정렬 알고리즘의 빠른 정렬을 고려합니다.이렇게 하면 입력으로 지정된 정수 목록을 정렬하는 문제가 해결됩니다.최악의 경우는 피벗이 항상 목록에서 가장 크거나 가장 작은 값인 경우입니다(따라서 목록이 분할되지 않음).이 경우 알고리즘은 시간 O(n)가² 걸립니다.입력 목록의 가능한 모든 배열이 같다고 가정할 경우 정렬에 걸리는 평균 시간은 O(n log n)입니다.최적의 경우는 각 피벗이 목록을 반으로 분할하고 O(n log n) 시간도 필요로 하는 경우입니다.

문제의 복잡성 상한 및 하한

계산 시간(또는 공간 소비와 같은 유사한 리소스)을 분류하려면 주어진 문제를 해결하기 위해 가장 효율적인 알고리즘에 필요한 최대 시간의 상한과 하한을 시연하는 것이 유용합니다.알고리즘의 복잡도는 일반적으로 달리 지정되지 않는 한 최악의 복잡도로 간주됩니다.특정 알고리즘의 분석은 알고리즘의 분석 분야에 속합니다.문제의 시간 복잡도에 대한 상한 T(n)를 표시하려면 실행 시간을 최대 T(n)로 하는 특정 알고리즘이 있다는 것만 표시하면 됩니다.그러나 하한은 주어진 문제를 해결하는 모든 가능한 알고리즘에 대해 기술하기 때문에 하한을 증명하는 것은 훨씬 더 어렵습니다."모든 가능한 알고리즘"이라는 문구는 현재 알려진 알고리즘뿐만 아니라 미래에 발견될 수 있는 모든 알고리즘을 포함합니다.문제의 하한 T(n)를 표시하려면 어떤 알고리즘도 T(n)보다 낮은 시간 복잡성을 가질 수 없음을 보여줘야 합니다.

상한과 하한은 일반적으로 상수 요인과 더 작은 항을 숨기는 큰 O 표기법을 사용하여 표시됩니다.이를 통해 경계가 사용된 계산 모델의 특정 세부 사항으로부터 독립되게 됩니다.예를 들어, T(n) = 7n² + 15n + 40이면, 빅 O 표기법에서는 T(n) = O²(n)로 쓴다.

복잡도 클래스

복잡도 클래스의 정의

복잡도 클래스는 관련된 복잡도 문제의 집합입니다.단순 복잡도 클래스는 다음 요인에 의해 정의됩니다.

• 계산 문제 유형:가장 일반적으로 사용되는 문제는 의사 결정 문제입니다.그러나 복잡도 클래스는 함수 문제, 계수 문제, 최적화 문제, 약속 문제 등을 기준으로 정의할 수 있습니다.
• 계산 모델:계산의 가장 일반적인 모델은 결정론적 튜링 기계이지만, 많은 복잡도 클래스는 비결정론적 튜링 기계, 부울 회로, 양자 튜링 기계, 단조 회로 등에 기초한다.
• 바인드 중인 리소스(또는 하나 이상) 및 바인딩된 리소스:이 두 특성은 일반적으로 "다항 시간", "대수 공간", "일정한 깊이" 등과 같이 함께 명시됩니다.

일부 복잡도 클래스는 이 프레임워크에 맞지 않는 복잡한 정의를 가지고 있습니다.따라서 일반적인 복잡도 클래스의 정의는 다음과 같습니다.

결정론적 튜링 기계가 시간 f(n) 내에 해결할 수 있는 일련의 결정 문제.(이 복잡도 클래스는 DTIME(f(n)이라고 불립니다).

그러나 위의 연산시간을 구체적인 함수 f(n)에 의해 제한하면 선택된 기계 모델에 의존하는 복잡도 클래스가 생성되는 경우가 많다.예를 들어 {xx x is any binary string} 언어는 멀티테이프 튜링 머신 상에서 선형 시간 내에 해결할 수 있지만 싱글테이프 튜링 머신 모델에서는 반드시 2차 시간이 필요합니다.실행 시간의 다항식 변화를 허용하면, 코밤-에드먼드의 논문은 "합리적이고 일반적인 두 계산 모델의 시간 복잡도는 다항식적으로 관련되어 있다"고 명시한다(골드라이히 2008, 1.2장).이것은 다항식 시간 내에 결정론적 튜링 기계에 의해 풀 수 있는 결정 문제의 집합인 복잡도 클래스 P의 기초를 형성한다.대응하는 기능 문제의 세트는 FP입니다.

중요 복잡도 클래스

알고리즘에 의해 사용되는 시간 또는 공간을 제한함으로써 많은 중요한 복잡도 클래스를 정의할 수 있습니다.이 방법으로 정의되는 의사결정 문제의 중요한 복잡도 클래스는 다음과 같습니다.

복잡도 클래스 계산 모형 자원 제약 결정론적 시간 DTIME(f(n)) 결정론적 튜링 기계 시간 O(f(n) P 결정론적 튜링 기계 시간 O(poly(n)) 제외 시간 결정론적 튜링 기계 시간poly(n) O(2) 비결정적 시간 NTIME(f(n)) 비결정론적 튜링 기계 시간 O(f(n) NP 비결정론적 튜링 기계 시간 O(poly(n)) 넥스트 타임 비결정론적 튜링 기계 시간poly(n) O(2)

복잡도 클래스 계산 모형 자원 제약 결정론적 공간 DSPACE(f(n)) 결정론적 튜링 기계 스페이스 O(f(n)) L 결정론적 튜링 기계 스페이스 O(log n) PSPACE 결정론적 튜링 기계 공간 O(poly(n)) 엑스페이스 결정론적 튜링 기계 스페이스poly(n) O(2) 비결정론적 공간 NSPACE(f(n)) 비결정론적 튜링 기계 스페이스 O(f(n)) NL 비결정론적 튜링 기계 스페이스 O(log n) NPSPACE 비결정론적 튜링 기계 공간 O(poly(n)) 넥스페이스 비결정론적 튜링 기계 스페이스poly(n) O(2)

로그 공간 클래스(필요한 경우)는 문제를 나타내는 데 필요한 공간을 고려하지 않습니다.

Savitch의 정리에 의해 PSPACE = NPSPACE 및 EXPSPACE = NEXPSPACE로 밝혀졌다.

다른 중요한 복잡도 클래스에는 확률론적 튜링 기계를 사용하여 정의된 BPP, ZPP 및 RP, 부울 회로를 사용하여 정의된 AC 및 NC, 양자 튜링 기계를 사용하여 정의된 BQP 및 QMA가 포함됩니다.#P는 (결정 문제가 아닌) 문제를 세는 중요한 복잡도 클래스입니다.IP 및 AM과 같은 클래스는 Interactive Proof 시스템을 사용하여 정의됩니다.ALL은 모든 의사결정 문제의 클래스입니다.

계층 정리

이와 같이 정의된 복잡도 클래스의 경우, 계산 시간에 대한 요구사항을 완화하는 것이 실제로 더 큰 일련의 문제를 정의한다는 것을 증명하는 것이 바람직하다.특히 DTIME(n)은 DTIME(n²)에 포함되지만 포함이 엄격한지 여부를 아는 것은 흥미로울 것이다.시간과 공간 요구사항의 경우, 이러한 질문에 대한 답은 각각 시간과 공간 계층 이론에 의해 주어진다.이들은 각각의 자원을 제약함으로써 정의된 클래스에 적절한 계층을 유도하기 때문에 계층 이론이라고 불립니다.따라서 하나의 클래스가 다른 클래스에 적절히 포함될 수 있는 복잡도 클래스의 쌍이 있습니다.이러한 적절한 집합 포함을 추론하면 해결할 수 있는 문제의 수를 늘리기 위해 얼마나 더 많은 시간 또는 공간이 필요한지 정량적으로 설명할 수 있습니다.

더 정확히 말하면, 시간 계층 정리는 다음과 같이 기술한다.

${\displaystyle \mathsf{D}}$ ${\displaystyle \mathsf{T}}$ ${\displaystyle \mathsf{I}}$ ${\displaystyle \mathsf{M}}$E (${\displaystyle f}$ (${\displaystyle n}$ )${\displaystyle d\mathsf{}}$ ${\displaystyle \mathsf{D}}$ T ${\displaystyle \mathsf{I}}$ ${\displaystyle \mathsf{M}}$E (${\displaystyle f}$ )${\displaystyle {\mathrm{2로그}}^{}}$ 2 ${\displaystyle {2\mathrm{}}^{}}$ (${\displaystyle }$f (${\displaystyle n}$ $){$ $display$ style { dTIME }{\$big ( n )$ }\$subsetneq${ $mathsf {DTIME}{\$big }($cdot)$

공간 계층 정리는 다음과 같이 기술한다.

${\displaystyle \mathsf{D}}$ S ${\displaystyle \mathsf{P}}$A ${\displaystyle \mathsf{C}\mathsf{E}}$ (${\displaystyle f}$ (${\displaystyle n}$ )${\displaystyle d\mathsf{}}$ D ${\displaystyle \mathsf{S}}$ ${\displaystyle \mathsf{P}}$ A ${\displaystyle \mathsf{C}\mathsf{E}}$ (${\displaystyle f}$ )${\displaystyle \mathrm{log로그}}$( (${\displaystyle f}$ (${\displaystyle n}$) $){$ $display${ $mathsf$ { DSPACE } { \ $big$( } \ $subsetneq${ $f$( n$){$f ( n $)$ } \ $space }$

시간과 공간 계층 정리는 복잡도 클래스의 대부분의 분리 결과의 기초를 형성합니다.예를 들어, 시간 계층 정리는 P가 EXPTIME에 엄밀하게 포함되어 있음을 알려주고, 공간 계층 정리는 L이 PSPACE에 엄밀하게 포함되어 있음을 알려준다.

축소

많은 복잡도 클래스는 감소 개념을 사용하여 정의됩니다.감소는 한 문제를 다른 문제로 변환하는 것입니다.그것은 어떤 문제가 다른 문제만큼이나 어렵다는 비공식적 개념을 포착한다.예를 들어, 문제 X를 Y에 대한 알고리즘을 사용하여 풀 수 있다면, X는 Y보다 어렵지 않으며, X는 Y로 줄어든다고 할 수 있습니다.쿡 감소, 카르프 감소 및 레빈 감소와 같은 감소 방법과 다항식 시간 감소 또는 로그 공간 감소와 같은 감소의 복잡성에 대한 한계에는 다양한 유형의 감소가 있다.

가장 일반적으로 사용되는 감소는 다항식 시간 감소입니다.즉, 축소 공정에 다항식 시간이 걸립니다.예를 들어 정수를 제곱하는 문제를 두 정수를 곱하는 문제로 줄일 수 있습니다.즉, 두 정수를 곱하는 알고리즘을 사용하여 정수를 제곱할 수 있습니다.실제로, 이것은 곱셈 알고리즘의 양쪽 입력에 동일한 입력을 줌으로써 이루어질 수 있다.따라서 제곱은 곱셈으로 줄일 수 있기 때문에 제곱은 곱셈보다 어렵지 않다는 것을 알 수 있습니다.

이는 복잡도 클래스에서 문제가 어렵다는 개념에 동기를 부여합니다.C의 모든 문제를 X로 줄일 수 있다면 문제 X는 문제 C의 클래스에 대해 어렵다.따라서 X의 알고리즘은 C의 문제를 해결할 수 있기 때문에 C의 문제는 X보다 어렵지 않습니다.어려운 문제의 개념은 사용되는 감소 유형에 따라 달라집니다.P보다 큰 복잡도 클래스의 경우 다항식 시간 축소가 일반적으로 사용됩니다.특히 NP에게 어려운 문제의 집합은 NP-하드 문제의 집합입니다.

문제 X가 C에 있고 C에 대해 어려운 경우 X는 C에 대해 완전하다고 합니다.이는 X가 C에서 가장 어려운 문제임을 의미합니다(많은 문제가 똑같이 어려울 수 있으므로 X가 C에서 가장 어려운 문제 중 하나라고 말할 수 있습니다).따라서 NP-완전 문제의 클래스는 P에 없을 가능성이 가장 높은 NP에서 가장 어려운 문제를 포함합니다.문제 P = NP가 해결되지 않기 때문에, 알려진 NP-완전 문제 δ를₂ 다른 문제 δ로₁ 줄일 수 있다면, δ에₁ 대한 알려진 다항식 시간 해법이 없다는 것을 나타낼 것이다.이는 δ에₁ 대한 다항식 시간 해법이 δ에₂ 대한 다항식 시간 해법을 산출하기 때문이다.마찬가지로, 모든 NP 문제를 집합으로 줄일 수 있기 때문에 다항식 시간에 풀 수 있는 NP-완전 문제를 찾는 것은 P = ^[3]NP라는 것을 의미합니다.

중요한 미해결 문제

P 대 NP 문제

복잡도 클래스 P는 종종 효율적인 알고리즘을 허용하는 계산 작업을 모델링하는 수학적 추상화로 보입니다.이 가설은 코밤-에드먼즈 논문이라고 불린다.한편 복잡도 클래스 NP는 부울 만족도 문제, 해밀턴 경로 문제, 정점 커버 문제 등 효율적인 알고리즘이 알려지지 않은 많은 문제를 포함하고 있다.결정론적 튜링 기계는 특별한 비결정론적 튜링 기계이기 때문에, P의 각 문제는 또한 클래스 NP의 구성원임을 쉽게 알 수 있다.

P가 NP인지 아닌지에 대한 질문은 ^[3]해답의 광범위한 함축성 때문에 이론 컴퓨터 공학에서 가장 중요한 미해결 질문 중 하나이다.답이 '그렇다'인 경우, 많은 중요한 문제들이 보다 효율적인 해결책을 가지고 있음을 보여줄 수 있습니다.여기에는 연산 연구의 다양한 유형의 정수 프로그래밍 문제, 물류에서의 ^[5]많은 문제, 생물학에서의 단백질 구조 예측, 순수 수학 ^[6]이론의 공식 증명을 찾는 능력이 포함됩니다.P 대 NP 문제는 클레이 수학 연구소가 제안한 밀레니엄 상 문제 중 하나입니다.그 ^[7]문제를 해결하는 데 100만 달러의 상금이 걸려 있다.

P 또는 NP-complete에 없는 NP의 문제

Ladner는 P np NP이면 NP에 P도 ^[4]NP-완전도 아닌 문제가 있음을 보여 주었다.이러한 문제를 NP-중간 문제라고 합니다.그래프 동형 문제, 이산 로그 문제 및 정수 인수분해 문제는 NP-중간으로 간주되는 문제의 예입니다.이러한 문제는 P에 없거나 NP-완전하다고 알려져 있지 않은 극소수의 NP 문제 중 일부입니다.

그래프 동형 문제는 두 개의 유한 그래프가 동형인지 여부를 결정하는 계산 문제이다.복잡도 이론에서 중요한 미해결 문제는 그래프 동형 문제가 P, NP-완전 또는 NP-중간 중 어느 쪽에 있는지이다.정답은 알 수 없지만 적어도 NP-완전하지 ^[8]않은 것으로 생각됩니다.그래프 동형이 NP-완전인 경우 다항식 시간 계층은 두 번째 ^[9]수준으로 축소됩니다.다항식 계층은 유한한 수준까지 붕괴되지 않는다고 널리 알려져 있기 때문에 그래프 동형사상은 NP-완전하지 않다고 여겨진다.Laszlo Babai와 Eugene Luks에 의해 이 문제에 대한 최적의 알고리즘은 정점이 n개인 그래프에 대해 실행 $시간$O$(2n$ log${\displaystyle {\sqrt{n}}^{}}$n$)$ {$displaystyle$O(2$^{\sqrt {$n$\log$ n}}}}}}}}를$$ 가집니다.다만, Babai의 최근 연구 결과에는 이에 ^[10]대한 새로운 관점이 있을 가능성이 있습니다.

정수 인수분해 문제는 주어진 정수의 소수 인수분해를 결정하는 계산 문제입니다.결정문제로 표현되는 것은 입력이 k보다 작은 소인수를 가지고 있는지 여부를 판단하는 문제입니다.효율적인 정수 인수분해 알고리즘은 알려져 있지 않으며, 이 사실은 RSA 알고리즘과 같은 몇 가지 최신 암호화 시스템의 기반이 됩니다.정수 인수분해 문제는 NP 및 co-NP(및 UP 및^[11] co-UP)에 있습니다.문제가 NP-완전인 경우 다항식 시간 계층은 첫 번째 수준으로 축소됩니다(즉, NP는 co-NP와 같음).정수 인수분해에서 가장 잘 알려진 알고리즘은${\displaystyle }$일반 숫자 필드 체(${\displaystyle {}^{}}$(${\displaystyle {\text{exception 25:}}^{}}$ 9${\displaystyle {\text{exception 25:}\text{exception 25:}}^{}}$)${\displaystyle {\text{exception 25:}}^{}}$(${\displaystyle {\text{exception 25:}}^{}}$ n${\displaystyle {\text{exception 25:}}^{}}$) 3${\displaystyle {\text{exception 25:}\text{exception 25:}}^{}}$( ${\displaystyle {\text{exception 25:}}^{}}$ )${\displaystyle {\sqrt[\mathrm{}]{{}^{}}}^{}}$ $displaystyle$ O$(e^{\left({\sqrt[{3}}{\frac {64}{9}}}\right)$ {$sqrt{3}}({$log})}}}}}}(\$sqrt${n$})})})$에 시간이 걸립니다.그러나 이 문제에 대해 가장 잘 알려진 양자 알고리즘인 쇼어 알고리즘은 다항식 시간에 실행됩니다.불행히도, 이 사실은 비양자 복잡도 클래스와 관련하여 문제가 어디에 있는지에 대해 많은 것을 말해주지 않습니다.

다른 복잡도 클래스 간의 분리

많은 알려진 복잡도 클래스가 불평등하다고 의심되지만 이는 증명되지 않았습니다.예를 들어 P np NP pp PP p PSPACE이지만 P = PSPACE일 수 있습니다.P가 NP와 같지 않으면 P도 PSPACE와 같지 않습니다.P와 PSPACE 사이에는 RP, BPP, PP, BQP, MA, PH 등 이미 알려진 복잡도 클래스가 다수 존재하기 때문에 이러한 복잡도 클래스가 모두1개의 클래스로 압축될 가능성이 있습니다.이들 계층 중 하나가 불평등하다는 것을 증명하는 것은 복잡성 이론의 큰 돌파구가 될 것이다.

같은 선에서, co-NP는 NP 문제의 보완 문제(예/아니오 답이 거꾸로 된 문제)를 포함하는 클래스이다.NP는 co-NP와 같지 않다고 생각되지만^[13] 아직 증명되지 않았습니다.이 두 가지 복잡도 클래스가 같지 않으면 P=co-P이므로 P는 NP와 같지 않습니다.따라서 P=NP이면 co-P=co-NP가 된다.

마찬가지로, L(로그 공간에서 풀 수 있는 모든 문제의 집합)이 P에 엄격히 포함되거나 P와 같은지는 알려지지 않았다.NL과 NC와 같은 복잡도 클래스가 여러 개 존재하며 서로 다른 클래스인지 동일한 클래스인지는 알 수 없습니다.

P와 BPP가 동일한 것으로 생각됩니다.단, BPP = NEXP일 경우 현재 열려 있습니다.

난해성

이론적으로는 해결할 수 있는 문제(예: 크지만 유한한 자원, 특히 시간)이지만 실제로는 어떤 해결책이 유용하기 위해 너무 많은 자원을 필요로 하는 문제는 다루기 어려운 ^[14]문제로 알려져 있다.반대로 실제로 해결할 수 있는 문제를 다루기 쉬운 문제, 즉 말 그대로 "처리할 수 있는 문제"라고 합니다.실현 불가능한 용어(문자 그대로 "할 수 없다")는 때때로 다루기 어려운 ^[15]용어와 상호 교환하여 사용되지만, 이는 수학적 ^[16]최적화에서 실현 가능한 해결책과 혼동될 위험이 있다.

다루기 쉬운 문제는 다항식 시간 해법(P, PTIME)을 가진 문제에서 자주 확인된다. 이것은 코밤-에드먼즈 논문으로 알려져 있다.이러한 의미에서 다루기 어려운 것으로 알려진 문제에는 EXPTIME-hard 문제가 포함된다.NP가 P와 동일하지 않으면 NP-하드 문제도 이 점에서 다루기 어렵습니다.

그러나 이 식별은 정확하지 않다.큰 정도 또는 큰 선행 계수를 가진 다항식 시간 해법은 빠르게 성장하며 실제 크기 문제에는 실용적이지 않을 수 있다.반대로, 천천히 성장하는 지수 시간 해법은 현실적인 입력에 실용적일 수도 있고, 최악의 경우 오랜 시간이 걸리는 해법은 짧은 시간이 걸릴 수도 있다.대부분의 경우 또는 평균적인 경우이므로 여전히 실용적입니다.P에 문제가 없다고 해도 문제의 큰 케이스가 모두 어려운 것은 아닙니다.또, 대부분의 케이스가 어려운 것도 아닙니다.예를 들어, Presburger 산술의 결정 문제는 P에 없는 것으로 나타났지만, 대부분의 경우 합리적인 시간에 문제를 해결하는 알고리즘이 작성되었다.마찬가지로 알고리즘은 2차 시간보다 짧은 시간에 광범위한 크기의 NP-완전 배낭 문제를 해결할 수 있으며, SAT 솔버는 NP-완전 부울 만족도 문제의 큰 인스턴스를 일상적으로 처리합니다.

지수 시간 알고리즘을 실제로 사용할 수 없는 이유를 확인하려면 중지하기 전에 두 가지 연산을 수행하는ⁿ 프로그램을 고려하십시오.예를 들어, 작은 n, 예를 들어 컴퓨터가 초당 10번의 연산을 한다고¹² 가정하면, 프로그램은 우주의 나이와 같은 크기인 약 4×10년¹⁰ 동안 실행됩니다.훨씬 더 빠른 컴퓨터를 사용하더라도, 이 프로그램은 매우 작은 사례에만 유용하며, 그런 점에서 문제의 난해성은 기술적 진보와는 다소 무관합니다.그러나 n이 상대적으로 커질 때까지 1.0001ⁿ 연산을 필요로 하는 지수 시간 알고리즘이 실용적입니다.

마찬가지로 다항식 시간 알고리즘이 항상 실용적인 것은 아닙니다.예를 들어 실행 시간이 n인¹⁵ 경우 효율적이라고 간주하는 것은 불합리하며 작은 인스턴스 이외에는 여전히 쓸모가 없습니다.실제로 n개 또는² n개의 알고리즘도 현실적인³ 규모의 문제에서는 종종 실용적이지 않습니다.

연속 복잡도 이론

연속 복잡도 이론은 수치 분석에서 연구한 바와 같이 이산화에 의해 근사된 연속 함수를 포함하는 문제의 복잡도 이론을 참조할 수 있다.수치^[17] 분석의 복잡성 이론의 한 가지 접근법은 정보 기반 복잡성이다.

연속 복잡도 이론은 연속 동적 시스템과 미분 ^[18]방정식을 사용하는 아날로그 계산의 사용에 대한 복잡도 이론도 참조할 수 있습니다.제어 이론은 계산의 한 형태로 간주될 수 있으며 미분 방정식은 연속 시간 및 하이브리드 이산 연속 시간 ^[19]시스템의 모델링에 사용된다.

역사

알고리즘 복잡도 분석의 초기 예는 1844년 가브리엘 라메에 의해 수행된 유클리드 알고리즘의 실행 시간 분석입니다.

알고리즘 문제의 복잡성에 대한 실제 연구가 시작되기 전에는 다양한 연구자들에 의해 수많은 기초가 마련되었다.이들 중 가장 영향력 있는 것은 1936년 앨런 튜링에 의한 튜링 기계의 정의로, 컴퓨터의 매우 강력하고 유연한 단순화로 밝혀졌다.

계산 복잡성에 대한 체계적인 연구의 시작은 Juris Hartmanis와 Richard E가 1965년에 발표한 "알고리즘의 계산 복잡성에 대하여"에 기인한다. 스턴스는 시간 복잡성과 공간 복잡성의 정의를 제시하고 계층 이론을 ^[20]증명했다.게다가 1965년에 Edmonds는 "좋은" 알고리즘을 입력 크기의 ^[21]다항식으로 제한되는 실행 시간으로 간주할 것을 제안했다.

특정한 경계 자원을 가진^[20] 튜링 기계가 해결할 수 있는 문제를 연구하는 초기 논문에는 존 마이힐의 선형 유계 오토마타 정의(1960년), 레이먼드 스멀리언의 기초 집합 연구(1961년), 실시간 계산에 대한 야마다 히사오의^[22] 논문(1962년) 등이 있다.이보다 앞서 소련 출신의 이 분야의 선구자 보리스 트라흐텐브로트(1956)는 또 다른 특정 복잡성 ^[23]측정을 연구했다.그가 기억하는 바로는:

하지만, [자동화 이론에 대한] 저의 초기 관심은 점점 더 계산의 복잡성, 즉 스위칭 이론에서 계승된 조합 방법의 흥미로운 융합을 위해 치워졌습니다. 알고리즘 이론의 개념적인 무기입니다.이러한 아이디어는 1955년 제가 "복잡도 측정"^[24]으로 일반적으로 알려진 "신호화 함수"라는 용어를 만들었을 때 이미 떠올랐습니다.

1967년 Manuel Blum은 계산 가능한 함수의 집합에 대한 복잡성 측정의 바람직한 특성을 지정하는 일련의 공리(현재는 Blum 공리)를 공식화했고, 소위 속도 증가 정리라고 불리는 중요한 결과를 증명했다.이 분야는 1971년 스티븐 쿡과 레오니드 레빈이 NP-완전한 실질적으로 관련된 문제의 존재를 증명하면서 번창하기 시작했다.1972년 리처드 카프는 그의 획기적인 논문인 "조합 문제들 사이의 축소"를 통해 이 아이디어를 한 단계 도약시켰습니다. 이 논문에서 그는 21개의 다양한 조합 및 그래프 이론 문제가 각각 계산 난해성으로 악명 높은 ^[25]NP-완전이라는 것을 보여주었습니다.

「 」를 참조해 주세요.

복잡성에 대응

• Wuppuluri, Shyam; Doria, Francisco A., eds. (2020), Unravelling Complexity: The Life and Work of Gregory Chaitin, World Scientific, doi:10.1142/11270, ISBN 978-981-12-0006-9, S2CID 198790362

레퍼런스

인용문

교재

• Arora, Sanjeev; Barak, Boaz (2009), Computational Complexity: A Modern Approach, Cambridge University Press, ISBN 978-0-521-42426-4, Zbl 1193.68112
• Downey, Rod; Fellows, Michael (1999), Parameterized complexity, Monographs in Computer Science, Berlin, New York: Springer-Verlag, ISBN 9780387948836^{[영구 데드링크]}
• Du, Ding-Zhu; Ko, Ker-I (2000), Theory of Computational Complexity, John Wiley & Sons, ISBN 978-0-471-34506-0
• Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 0-7167-1045-5
• Goldreich, Oded (2008), Computational Complexity: A Conceptual Perspective, Cambridge University Press
• van Leeuwen, Jan, ed. (1990), Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, ISBN 978-0-444-88071-0
• Papadimitriou, Christos (1994), Computational Complexity (1st ed.), Addison Wesley, ISBN 978-0-201-53082-7
• Sipser, Michael (2006), Introduction to the Theory of Computation (2nd ed.), USA: Thomson Course Technology, ISBN 978-0-534-95097-2

조사

• Khalil, Hatem; Ulery, Dana (1976), "A Review of Current Studies on Complexity of Algorithms for Partial Differential Equations", Proceedings of the Annual Conference on - ACM 76, ACM '76: 197–201, doi:10.1145/800191.805573, ISBN 9781450374897, S2CID 15497394
• Cook, Stephen (1983), "An overview of computational complexity", Commun. ACM, 26 (6): 400–408, doi:10.1145/358141.358144, ISSN 0001-0782, S2CID 14323396
• Fortnow, Lance; Homer, Steven (2003), "A Short History of Computational Complexity" (PDF), Bulletin of the EATCS, 80: 95–133
• Mertens, Stephan (2002), "Computational Complexity for Physicists", Computing in Science and Eng., 4 (3): 31–47, arXiv:cond-mat/0012185, Bibcode:2002CSE.....4c..31M, doi:10.1109/5992.998639, ISSN 1521-9615, S2CID 633346

외부 링크

• 복잡성 동물원
• "Computational complexity classes", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• 복잡성 이론에서 모든 사람이 알아야 할 가장 중요한 결과(및 논문)는 무엇입니까?
• 스콧 애런슨:철학자들이 계산의 복잡성에 관심을 가져야 하는 이유