보완(복잡성)

Complement (complexity)

계산 복잡성 이론에서 의사결정 문제의 보완점은 예스 앤 노 해답의 역순으로 인한 의사결정 문제다.[1]마찬가지로, 의사결정 문제를 유한 문자열 집합으로 정의한다면, 고정된 영역에 대한 이 집합의 보완점은 그것의 보완 문제일 것이다.[2]

예를 들어, 한 가지 중요한 문제는 숫자가 소수인지 여부다.그것의 보완점은 숫자가 복합적인 숫자인지 아닌지를 결정하는 것이다.여기서 보완의 영역은 1을 초과하는 모든 정수의 집합이다.[3]

모든 문제에서 그것의 보완적인 문제로 튜링의 감소가 있다.[4]보완작전은 본래의 문제로서, '자신이 풀린다'는 뜻이며, 또는 보완작전이 본래의 문제라는 뜻이다.

사람들은 이것을 수업의 모든 문제들에 대한 보충의 집합인 보충수업이라고 불리는 복잡성 계층의 보충수업으로 일반화할 수 있다.[5]한 클래스를 C라고 부르면, 그 보완물은 관례적으로 co-C라고 부르게 된다.이것은 일련의 문제로서 복잡성 등급 자체를 보완하는 것이 아니며, 이는 훨씬 더 많은 문제를 포함할 것이다.

수업은 수업 중 어떤 문제의 보충이 아직 수업 중이라면 보충수업으로 휴강한다고 한다.[6]모든 문제에서 보완으로 튜링 감소가 있기 때문에 튜링 감소에 따라 마감되는 모든 클래스는 보완에 따라 마감된다.보어 밑에 닫힌 등급은 보어 등급과 같다.그러나 많은 1개 감축 하에서 많은 중요한 계층, 특히 NP는 (이것이 증명되지는 않았지만) 보충 계층과 구별되는 것으로 생각된다.[7]

튜링 감소에 따른 모든 복잡성 등급의 폐쇄는 보완에 따라 닫히는 해당 클래스의 상위 집합이다.그러한 등급은 보완 아래 폐쇄된 것이 가장 작다.클래스와 해당 클래스가 교차하는 경우, 우리는 (비어 있을 가능성이 있는) 부분 집합을 얻는데, 이 부분 집합은 보완 아래에 닫힌다.

모든 f(n)에 대한 모든 결정론적 복잡성 등급(DSPACE(f(n)), DTIME(f(n)))은 보완 하에서 닫힌다.[8] 왜냐하면 단순히 답을 뒤집는 알고리즘에 마지막 단계를 추가할 수 있기 때문이다.이는 비결정론적 복잡성 클래스에서는 작동하지 않는데, 이는 수용 경로와 거부 경로가 모두 존재하며, 모든 경로가 그들의 대답을 반대로 한다면, 여전히 수용 경로와 거부 경로가 존재하기 때문이다. 결과적으로 기계는 두 가지 경우 모두 수용하게 된다.

지금까지 보여진 가장 놀라운 복잡성 결과 중 일부는 복잡성 등급 NL과 SL이 실제로 보완 하에 닫힌 반면, 일반적으로 그렇지 않다고 여겨지기 전에는 그렇지 않다는 것을 보여주었다(Immerman-Szepcsnei 정리 참조).우리가 SL과 결정론적 등급인 L을 동일시하고 있다는 것을 알게 된 지금 후자는 덜 놀라워졌다.

스스로 낮은 수업은 모두 보충수업으로 마감된다.

참조

  1. ^ Itô, Kiyosi (1993), Encyclopedic Dictionary of Mathematics, Volume 1, MIT Press, p. 269, ISBN 9780262590204.
  2. ^ Schrijver, Alexander (1998), Theory of Linear and Integer Programming, Wiley Series in Discrete Mathematics & Optimization, John Wiley & Sons, p. 19, ISBN 9780471982326.
  3. ^ Homer, Steven; Selman, Alan L. (2011), Computability and Complexity Theory, Texts in Computer Science, Springer, ISBN 9781461406815.
  4. ^ Singh, Arindama (2009), Elements of Computation Theory, Texts in Computer Science, Springer, Exercise 9.10, p. 287, ISBN 9781848824973.
  5. ^ Bovet, Daniele; Crescenzi, Pierluigi (1994), Introduction to the Theory of Complexity, Prentice Hall International Series in Computer Science, Prentice Hall, pp. 133–134, ISBN 9780139153808.
  6. ^ Vollmer, Heribert (1999), Introduction to Circuit Complexity: A Uniform Approach, Texts in Theoretical Computer Science. An EATCS Series, Springer, p. 113, ISBN 9783540643104.
  7. ^ Pruim, R.; Wegener, Ingo (2005), Complexity Theory: Exploring the Limits of Efficient Algorithms, Springer, p. 66, ISBN 9783540274773.
  8. ^ Ausiello, Giorgio (1999), Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer, p. 189, ISBN 9783540654315.