맨위로가기

P (복잡도)

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

P는 결정론적 튜링 기계로 다항 시간 내에 풀 수 있는 판정 문제들의 집합을 의미한다. P는 다항 시간 균일 불 대수 회로 집합으로도 정의될 수 있으며, NP, co-NP, L, PSPACE, EXPTIME 등 다른 복잡도 종류들과 관계를 가진다. P에 속하는 문제로는 선형 계획법, 최대 매칭, 소수 판별 등이 있으며, 다항 시간 알고리즘은 합성에 대해 닫혀 있고, P는 자기 자신에 대해 낮다는 특징을 가진다.

2. 정의

형식 언어 ''L''이 P에 속한다는 것은, 다음과 같은 조건을 만족하는 결정론적 튜링 기계 ''M''이 존재한다는 것과 동치이다.


  • ''M''은 모든 입력에 대해 다항 시간 내에 실행된다.
  • ''L''에 속하는 모든 ''x''에 대해 ''M''은 1을 출력한다.
  • ''L''에 속하지 않는 모든 ''x''에 대해 ''M''은 0을 출력한다.


P는 또한 균일한 불 대수 회로 집합으로 볼 수 있다. 언어 ''L''이 P에 속한다는 것은, 다음과 같은 조건을 만족하는 다항 시간 균일 불 대수 회로 집합 \{C_n:n \in \mathbb{N}\}이 존재한다는 것과 동치이다.

  • 모든 n \in \mathbb{N}에 대해, C_n은 ''n'' 비트를 입력으로 받아 1 비트를 출력한다.
  • ''L''에 속하는 모든 ''x''에 대해, C_

    (x)=1
  • ''L''에 속하지 않는 모든 ''x''에 대해, C_

    • (x)=0

    회로 정의는 로그 공간 균일 집합만을 사용하여 복잡도 클래스를 변경하지 않고 약화될 수 있다.

    판정 문제 중, 어떤 결정적 튜링 기계에 의해 다항 시간 내에 풀리는 문제 전체를 '''P'''로 나타낸다.

    3. 다른 복잡도 종류와의 관계

    NP는 비결정론적 튜링 기계로 다항 시간 안에 풀 수 있는 판정 문제들의 집합이며, 이 문제들은 결정론적 튜링 기계로 다항 시간 안에 답을 검증할 수 있다. P는 NP의 부분집합이지만, P와 NP가 같은지 아닌지는 아직 알려지지 않았다. 이 문제는 P-NP 문제라고 부른다.[3] P는 NP와 co-NP의 부분집합이다. 대부분 P가 진부분집합이라고 믿지만, 증명되지는 않았다.

    L은 결정론적 튜링 기계로 로그 메모리 공간을 사용하여 풀 수 있는 판정 문제들의 집합으로, P의 부분집합으로 알려져 있지만 P와 L이 같은지 아닌지는 미해결 상태이다.

    ALOGSPACE는 교대 튜링 기계가 로그 메모리를 써서 풀 수 있는 문제들의 집합으로, P=ALOGSPACE는 증명되어 있다. P는 또한 다항 공간에서 결정 가능한 문제의 클래스인 PSPACE보다 크지 않은 것으로 알려져 있다. P = PSPACE인지 여부는 미해결 문제이다.

    EXPTIME은 지수 시간 안에 풀 수 있는 판정 문제들의 집합으로, P는 EXPTIME의 진부분집합임이 증명되어 있다.

    이를 수식으로 나타내면 다음과 같다.

    :\mbox{L} \subseteq \mbox{ALOGSPACE} = \mbox{P} \subseteq \mbox{NP} \subseteq \mbox{PSPACE} \subseteq \mbox{EXPTIME}

    P가 EXPTIME과 같지 않기 때문에, 위의 포함 관계 중 적어도 하나는 진부분집합 관계여야 한다.

    P에서 가장 어려운 문제는 P-완전 문제이다.

    P를 일반화한 것에는 P/poly (비균일 다항시간)가 있다. P/poly에 속한 문제는 입력의 길이에 의존하는 조언 문자열이 주어지면 결정론적 다항시간에 풀 수 있다. P/poly는 BPP를 포함하여 거의 모든 실제 문제를 포함하는 큰 클래스이다.

    P, NP, co-NP, BPP, P/poly, PH, PSPACE를 포함하는 복잡도 클래스의 포함 관계


    확률적 복잡도 클래스( ZPP, RP, co-RP, BPP, BQP, PP)와 관련된 P, 모두 PSPACE 내에 있다. 이러한 포함 관계가 엄격한지는 알 수 없다.


    P는 BQP에 포함된다. 이 포함 관계가 엄격한지는 알 수 없다.

    4. P의 성질

    다항 시간 알고리즘은 합성(composition영어)에 대해 닫혀 있다. 직관적으로 설명하면, 다항 시간 안에 실행되는 함수를 만들어서 이 함수를 상수 번만큼 불러서 사용하고, 함수를 불러서 사용하는 알고리즘도 다항 시간의 시간이 걸리면 전체 실행 시간은 여전히 다항 시간이다. 이런 이유로 '''P'''는 자기 자신에 대해서 낮다. 예를 들어서 임의 접근이 가능한 특정한 기계는 메모리에 접근하는 다항 시간 과정을 메모리에 순서대로 접근하는 다항 시간으로 흉내 낼 수 있기 때문에 순차 접근 기계를 합성하여 임의 접근 기계를 만들 수 있다.

    P에 속하는 언어는 역, 교집합, 합집합, 연결, 클레이니 스타, 역 준동형 사상, 그리고 여집합에 대해서도 닫혀 있다.[6]

    5. P의 일반화

    '''P/poly'''는 '''비균일 다항 시간'''(Nonuniform Polynomial-Time영어)이라고도 한다. P/poly에 속한 문제는 입력 길이에 의존하는 조언 문자열이 주어지면 결정론적 다항 시간에 풀 수 있다. 그러나 NP와 달리 다항 시간 기계가 검증 기계가 아니므로 거짓 조언 문자열인지 찾아낼 필요는 없다. P/poly는 거의 모든 효율적인 알고리즘을 포함하는 큰 집합이다. 모든 BPP도 P/poly에 포함된다. 만약 NP도 P/poly에 포함되면, 다항 위계 전체가 오직 두 단계로 줄어든다. 반면에, 모든 판정 불가능 문제들의 단항 버전 같은 일부 판정 불가능 문제도 P/poly에 포함된다.

    P에 대응하는 함수 문제 복잡도 종류에는 FP가 있다.

    6. P에 속하는 주목할 만한 문제들

    P는 선형 계획법의 결정 버전과 최대 매칭을 포함하여 많은 자연스러운 문제를 포함하는 것으로 알려져 있다. 2002년에는 숫자가 소수인지 판별하는 문제가 P에 속한다는 것이 밝혀졌다.[1] 관련 클래스인 함수 문제는 FP이다.

    몇 가지 자연스러운 문제는 P에 대해 완전하며, ''st''-연결성 (또는 접근 가능성)을 교대 그래프에서 계산하는 문제가 있다.[2]

    7. 다른 관련 클래스

    NP는 비결정론적 튜링 기계로 다항 시간 안에 풀 수 있는 판정 문제들의 집합으로, 결정론적 튜링 기계로 다항 시간 안에 답을 검증할 수 있다. P는 NP의 부분집합이지만, P와 NP가 같은지 아닌지는 아직 알려지지 않았다. (P-NP 문제)[1]

    L은 결정론적 튜링 기계로 로그 메모리 공간을 사용하여 풀 수 있는 판정 문제들의 집합으로, P의 부분집합으로 알려져 있지만 P와 L이 같은지 아닌지는 아직 미해결 상태이다.[1]

    ALOGSPACE는 교대 튜링 기계가 메모리를 로그만큼 써서 풀 수 있는 문제들의 집합으로, P=ALOGSPACE라는 것은 증명되어 있다. PSPACE는 다항 공간을 사용하여 풀 수 있는 판정 문제의 집합으로, P는 PSPACE의 부분집합이지만 이 두 집합이 같은지에 대해서는 아직 미해결 상태이다. L이 PSPACE의 진부분집합이라는 것은 증명되어 있다.[1]

    EXPTIME은 지수 시간 안에 풀 수 있는 판정 문제들의 집합으로, P는 EXPTIME의 진부분집합이라는 것이 증명되어 있다. 또한 모든 EXPTIME-난해 문제는 P에 속하지 않는다.[1]

    이를 수식으로 표기하면 다음과 같다.

    :\mbox{L} \subseteq \mbox{ALOGSPACE} = \mbox{P} \subseteq \mbox{NP} \subseteq \mbox{PSPACE} \subseteq \mbox{EXPTIME}

    또한 위 관계에서 P가 EXPTIME과 같지 않기 때문에, \mbox{P} \subseteq \mbox{NP}, \mbox{NP} \subseteq \mbox{PSPACE}, \mbox{PSPACE} \subseteq \mbox{EXPTIME} 중 최소한 하나는 진부분집합 관계여야 한다.[1]

    P에 속한 가장 어려운 문제는 P-완전 문제이다.[1]

    P를 일반화한 것에는 P/poly도 있다. '''P/poly'''는 '''비균일 다항시간'''(Nonuniform Polynomial-Time영어)이라고도 한다. P/poly에 속한 문제는 입력의 길이에 의존하는 조언 문자열이 주어지면 결정론적 다항시간에 풀 수 있다. P/poly는 거의 모든 효율적인 알고리즘을 포함하는 큰 집합이다. 모든 BPP도 P/poly에 포함된다. 만약 NP도 P/poly에 포함되면, 다항 위계 전체가 오직 두 단계로 줄어든다. 반면에, 모든 판정불가능 문제들의 단항 버전 같은 일부 판정불가능 문제도 P/poly에 포함된다.[1]

    P에 대응하는 함수 문제 복잡도 종류에는 FP가 있다.[1]

    다음은 요약에 언급된 복잡도 클래스들이다.


    • 클래스 NP - 제시된 답의 검증이 클래스 P가 되는 결정 문제의 클래스.[1]
    • 클래스 FP - 클래스 P와 유사한 개념이지만, 클래스 P와는 달리 해를 출력할 수 있는 문제의 클래스.[1]
    • 클래스 RP - 답이 no일 때는 반드시 no로 반환하지만, 답이 yes일 때는 어떤 확률로 no라고 답할 수 있는 확률적 알고리즘에 의해 해결되는 판정 문제의 클래스. 몬테카를로 방법 등의 기법을 계산 이론상으로 해석하기 위해 생겨났다.[1]
    • 다항식 계층[1]

    8. 다른 특징들

    서술적 복잡도에서 P는 정렬된 구조에 최소 고정점 연산자가 추가된 1차 논리인 FO(LFP)로 표현 가능한 문제로 설명될 수 있다. 1999년 서술적 복잡도 교과서에서 이 결과는 Vardi와 Immerman의 연구 결과로 언급되었다.[7][8][9]

    2001년에는 PTIME이 (양의) 범위 연결 문법에 해당한다는 것이 발표되었다.[10]

    P는 결정 문제가 아닌 문제에 대한 알고리즘 복잡도 클래스로 정의될 수도 있다.[11] 예를 들어, 2-만족성 인스턴스에 대한 해를 다항 시간 내에 찾는 것은 자동으로 해당 결정 문제에 대한 다항 알고리즘을 제공한다. 이 경우 P는 NP의 부분 집합이 아니지만, P∩DEC는 NP의 부분 집합이며, 여기서 DEC는 결정 문제 클래스이다.

    9. 역사

    코젠[12]은 코밤과 에드몬즈가 일반적으로 다항 시간의 개념을 발명한 것으로 여겨진다고 언급했다. 코밤은 효율적인 알고리즘을 특징짓는 강력한 방법으로 이 클래스를 발명했고, 이는 코밤의 테제로 이어졌다. 그러나, H. C. 포클링턴은 1910년 논문에서[13][14] 이차 합동식을 푸는 두 가지 알고리즘을 분석하면서, 다항 시간 알고리즘과 지수 시간 알고리즘의 구분을 제시했다.

    참조

    [1] 논문 PRIMES is in P http://www.cse.iitk.[...] Annals of Mathematics 2004
    [2] 서적 Descriptive Complexity Springer-Verlag
    [3] 서적 Algorithms Pearson Education
    [4] 웹사이트 complexity theory - Why is co-P = P https://stackoverflo[...] 2020-10-14
    [5] 간행물 Sparse Hard Sets for P: Resolution of a Conjecture of Hartmanis 1999-04
    [6] 서적 Introduction to automata theory, languages, and computation Addison-Wesley
    [7] 서적 Descriptive Complexity Springer-Verlag
    [8] conference The Complexity of Relational Query Languages
    [9] conference Relational Queries Computable in Polynomial Time
    [10] 서적 Parsing Beyond Context-Free Grammars Springer Science & Business Media
    [11] 서적 Complexity Theory Springer-Verlag
    [12] 서적 Theory of Computation Springer
    [13] 간행물 The determination of the exponent to which a number belongs, the practical solution of certain congruences, and the law of quadratic reciprocity
    [14] 서적 Mathematics of computation, 1943–1993: a half-century of computational mathematics: Mathematics of Computation 50th Anniversary Symposium, August 9–13, 1993, Vancouver, British Columbia American Mathematical Society
    [15] 저널 인용 PRIMES is in P http://www.cse.iitk.[...]


    본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
    모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
    하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
    따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

    문의하기 : help@durumis.com