경감(복잡도)

Reduction (complexity)
부울 만족도 문제(A b B)에서 정점 커버 문제(A ) B b C)로 축소된 예.파란색 정점은 최소 정점 커버를 형성하고 회색 타원형의 파란색 정점은 원래 공식에 대한 만족스러운 진실 할당에 해당합니다.

계산 가능성 이론과 계산 복잡도 이론에서, 감소는 한 문제를 다른 문제로 변환하기 위한 알고리즘이다.한 문제에서 다른 문제로 충분히 효율적인 감소를 사용하여 두 번째 문제가 적어도 첫 번째 문제만큼 어렵다는 것을 나타낼 수 있습니다.

직관적으로 문제 A를 효율적으로 해결하기 위한 알고리즘이 문제 A를 효율적으로 해결하기 위한 서브루틴으로도 사용될 수 있다면 문제 A는 문제 B로 환원될 수 있다.이것이 사실이라면, A를 해결하는 것은 B를 해결하는 것보다 더 어려울 수 없습니다. "하드"는 주어진 상황에서 필요한 계산 자원을 더 많이 추정하는 것을 의미합니다(예를 들어, 단일 스레드 솔루션에 비해 더 높은 시간 복잡성, 더 큰 메모리 요건, 추가 하드웨어 프로세서 코어의 필요성 등).A에서 B로의 축소의 존재는 A mb B로 표기할 수 있습니다.보통 사용하는 축소의 유형을 나타내기 위해 to에 첨자를 붙입니다(m : mapping reduction, p : 다항식 reduction).

특정 유형의 축소에 의해 일련의 문제에 대해 생성된 수학적 구조는 일반적으로 사전 순서를 형성하며, 그 동등성 클래스는 분해 불가능성과 복잡성 클래스의 정도를 정의하기 위해 사용될 수 있다.

서론

감축을 사용해야 하는 상황은 주로 두 가지입니다.

  • 첫째, 우리는 우리가 이미 해결한 문제와 비슷한 문제를 해결하려고 노력합니다.이 경우 새로운 문제를 해결하는 빠른 방법은 새로운 문제의 각 인스턴스를 오래된 문제의 인스턴스로 변환하고 기존 솔루션을 사용하여 문제를 해결한 후 이를 사용하여 최종 솔루션을 얻는 것입니다.이것은 아마도 가장 명백한 감축의 사용일 것이다.
  • 둘째, 해결이 어렵다는 것을 증명한 문제가 있다고 가정해 봅시다.그리고 비슷한 새로운 문제도 있습니다.우리는 그것 또한 해결하기 어렵다고 의심할 수 있다.우리는 모순으로 논쟁한다: 새로운 문제가 해결되기 쉽다고 가정하자.그리고 오래된 문제의 모든 경우를 새로운 문제의 사례로 변환하여 해결함으로써 쉽게 해결할 수 있다는 것을 보여줄 수 있다면 모순이 있습니다.이것은 새로운 문제도 어렵다는 것을 증명한다.

감소의 매우 간단한 예는 곱셈에서 제곱까지입니다.더하기, 빼기, 제곱하기, 그리고 2로 나누는 방법밖에 없다고 가정합니다.이 지식을 다음 공식과 조합하여 임의의 두 숫자의 곱을 구할 수 있습니다.

다른 방향에서도 감소가 있습니다. 두 숫자를 곱할 수 있다면, 당연히 수를 제곱할 수 있습니다.이것은 이 두 문제가 똑같이 어렵다는 것을 암시하는 것으로 보인다.이러한 종류의 감소는 튜링 감소에 해당합니다.

그러나 제곱 함수를 1회만 사용할 수 있고, 마지막에만 사용할 수 있다는 제한을 더하면 감소가 더 어려워집니다. 경우 곱셈을 포함한 모든 기본적인 산술 연산을 사용할 수 있어도 일반적으로 감소는 존재하지 않습니다. 왜냐하면 제곱근으로서 원하는 결과를 얻으려면 먼저 제곱근을 계산해야 하고 이 제곱근은 2와 무리수일수 있기 때문입니다유리수에 대한 산술 연산에 의해 방해된다.하지만 다른 방향으로 가면, 우리는 한 곱셈만으로 숫자를 제곱할 수 있습니다. 마지막 곱셈에서만요.이 제한적인 축소 형식을 사용하여 곱셈이 제곱보다 일반적으로 어렵다는 놀라운 결과를 보여 주었다.이것은 다원적인 삭감에 해당합니다.

특성.

감소는 P(N)×P(N) 상에서 사전순서, 즉 반사적이고 전이적인 관계이며, 여기서 P(N)는 자연수의 멱집합이다.

삭감 종류 및 적용

위의 예에서 설명한 바와 같이, 계산 복잡도에 사용되는 두 가지 주요 감소 유형이 있습니다. 다원 감소와 튜링 감소입니다.다일 축소는 한 문제의 인스턴스를 다른 문제의 인스턴스에 매핑합니다. 튜링 축소는 다른 문제를 해결하기 쉽다고 가정할 때 하나의 문제에 대한 해결책을 계산합니다.다원 감소는 튜링 감소의 더 강력한 유형으로, 문제를 별개의 복잡도 클래스로 분리하는 데 더 효과적입니다.그러나, 다일제 축소에 대한 규제가 증가함에 따라, 그것을 찾는 것이 더욱 어려워지고 있다.

복잡도 클래스의 모든 문제가 해당 문제로 축소되고 클래스 자체에도 문제가 있는 경우 문제가 완료됩니다.이러한 의미에서 문제는 클래스를 나타냅니다.왜냐하면 이 문제에 대한 어떤 해결책도 감소와 함께 클래스 내의 모든 문제를 해결하기 위해 사용될 수 있기 때문입니다.

그러나 유용하게 쓰려면 감소가 쉬워야 합니다.예를 들어, 리덕션 머신을 통해 지수 시간 내에 문제를 해결하고 해결책이 있는 경우에만 0을 출력함으로써 부울 만족도 문제와 같은 해결이 어려운 NP-완전 문제를 사소한 문제로 줄일 수 있습니다.그러나 새로운 문제를 해결할 수 있지만 감축을 수행하는 것은 오래된 문제를 해결하는 것만큼 어렵기 때문에 이것은 큰 성과를 거두지 못합니다.마찬가지로, 계산 불가능한 함수를 축소 계산하면 결정 불가능한 문제를 결정 가능한 문제로 줄일 수 있습니다.Michael Sipser가 '계산 이론 소개'에서 지적했듯이, "클래스의 일반적인 문제의 복잡성에 비해 감소는 쉬워야 합니다.[...] 감소 자체가 계산하기 어려웠다면, 완전한 문제에 대한 쉬운 해결책이 반드시 감소하는 문제에 대한 쉬운 해결책을 제시하지는 못할 것입니다."

따라서 적절한 감소 개념은 연구 중인 복잡도 클래스에 따라 달라집니다.복잡도 클래스 NP 및 다항식 계층구조와 같은 더 어려운 클래스를 연구할 때 다항식 시간 축소가 사용됩니다.NC, NL과 같은 P 내의 클래스를 학습할 때 로그 공간 축소를 사용합니다.감소는 또한 계산 가능성 이론에서 문제가 기계에 의해 해결될 수 있는지 여부를 보여주기 위해 사용됩니다. 이 경우 감소는 계산 가능한 함수로만 제한됩니다.

최적화(최대화 또는 최소화) 문제의 경우, 우리는 종종 근사 보존 감소라는 관점에서 생각한다.한 문제의 인스턴스를 다른 문제의 인스턴스에 매핑할 수 있고, 후자의 문제에 대한 거의 최적의 솔루션을 다시 변환하여 전자에 대한 거의 최적의 솔루션을 얻을 수 있는 두 가지 최적화 문제가 있다고 가정합니다.이와 같이 문제 B의 인스턴스에 대한 거의 최적의(또는 최적의) 솔루션을 찾고 문제 A에서 문제 B로의 효율적인 근사 보존 감소를 찾는 최적화 알고리즘(또는 근사 알고리즘)이 있는 경우, 구성에 의해 문제 A의 인스턴스에 대해 거의 최적의 솔루션을 산출하는 최적화 알고리즘을 얻을 수 있습니다.근사 보존 감소는 종종 근사 결과의 경도를 증명하기 위해 사용된다. 일부 최적화 문제 A가 일부 α에 대해 α보다 나은 인자 내에서 근사하기 어렵고(일부 복잡도 가정 하에서), 문제 A에서 문제 B로 β 근사 보존 감소가 있는 경우, 문제 B는 근사하기 어렵다는 결론을 내릴 수 있다.α/β인자 내에서 근사한다.

예

  • 결정 문제 P가 결정 불가능하다는 것을 보여주기 위해 우리는 이미 P에게 결정 불가능하다고 알려진 결정 문제에서 감소를 찾아야 한다.그 축소 함수는 계산 가능한 함수여야 한다.특히, 우리는 종종 정지 문제가 P로 감소함을 보여줌으로써 문제 P를 결정할 수 없다는 것을 보여준다.
  • 복잡도 클래스 P, NP 및 PSPACE는 다항식 시간 감소로 닫힙니다.
  • 복잡도 클래스 L, NL, P, NP 및 PSPACE는 로그 공간 감소로 닫힙니다.

상세한 예

다음 예시는 언어를 결정할 수 없음을 증명하기 위해 정지 문제에서 축소를 사용하는 방법을 보여 줍니다.H(M, w)가 입력 문자열 w에 대해 주어진 튜링 기계 M이 정지하는지(승인 또는 거부함으로써) 결정하는 문제라고 가정합니다.이 언어는 판별할 수 없는 것으로 알려져 있다.E(M)가 주어진 튜링 기계 M이 받아들이는 언어가 비어 있는지(즉, M이 어떤 문자열을 받아들이는지)를 결정하는 문제라고 가정합니다.우리는 E가 H에서 감소하여 결정되지 않는다는 것을 보여준다.

모순을 얻기 위해 R이 E의 결정자라고 가정합니다.이것을 사용하여 H에 대한 Decider S(존재하지 않는 것을 알고 있습니다)를 제작합니다.입력 M과 w(튜링 머신과 일부 입력 문자열)가 주어지면 S(M, w)를 다음 동작으로 정의한다.S는 N에 대한 입력 문자열이 w이고 M이 입력 w에 정지하고 그 이외의 경우에는 정지하지 않는 경우에만 받아들이는 튜링 머신 N을 생성한다.이제 Decider S는 R(N)을 평가하여 N이 받아들이는 언어가 비어 있는지 여부를 확인할 수 있습니다.R이 N을 받아들이면 N이 받아들이는 언어는 비어 있기 때문에 특히 M은 입력w로 정지하지 않기 때문에 S는 거부할 수 있습니다.R이 N을 거부하면 N에 의해 받아들여진 언어는 공백이 아니기 때문에 M은 입력w로 정지하기 때문에 S가 받아들일 수 있습니다.따라서 E에 대한 Decider R이 있으면 임의의 머신 M과 입력 w에 대해 정지 문제 H(M, w)에 대한 Decider S를 생성할 수 있습니다.이러한 S는 존재할 수 없다는 것을 알고 있기 때문에, 언어 E도 결정할 수 없습니다.

「 」를 참조해 주세요.

레퍼런스

  • 토마스 H. 코먼, 찰스 E.Leiserson, Ronald L. Rivest 및 Clifford Stein, 알고리즘 소개, MIT Press, 2001, ISBN978-0-262-03293-3
  • 하틀리 로저스 주니어:재귀함수와 유효계산성 이론, McGraw-Hill, 1967, ISBN 978-0-262-68052-3.
  • Peter Bürgisser:대수적 복잡도 이론의 완전성과 감소, 2000, ISBN 978-3-540-66752-0.
  • E.R. Griffor: 계산가능성 이론 핸드북, 1999, ISBN 978-0-444-89882-1.