비건설 알고리즘 존재 증명

Non-constructive algorithm existence proofs

계산 문제에 대한 대부분의 긍정적인 결과는 건설적인 증명이다. 즉, 계산 문제는 그것을 해결하는 알고리즘을 보여줌으로써 해결할 수 있다는 것을 증명한다. 계산 문제는 입력 크기의 다항식인 시간에 그것을 해결하는 알고리즘을 보여줌으로써 P(복잡성)에 있는 것으로 나타난다.

그러나 알고리즘 자체를 보여주지 않고 알고리즘이 존재한다는 것을 증명하는 몇 가지 비구축적 결과가 있다.그러한 존재 증거를 제공하기 위해 몇 가지 기법이 사용된다.

알 수 없는 유한 집합 사용

콤비네이터 게임 이론에서

비구축 알고리즘의 간단한 예는 Elwyn R에 의해 1982년에 출판되었다. Berlekamp, John H. Conway, Richard K. '수학극의 승리 방법'이란 책에서 말이야앞서 지정한 값의 합으로 표현할 수 없는 양의 정수를 번갈아 지정해 숫자 1을 지정하도록 강요받으면 지는 실버 코인게이지의 경기에 관한 것이다.주어진 첫 번째 동작이 승패를 가르는 알고리즘(흐름표로서 책에 제시된)이 존재한다. 세 개 이상의 프라임 숫자 또는 3-스무스한 수의 유한 집합 중 하나라면 승리하는 첫 동작이고, 그렇지 않으면 패한다.그러나 유한한 집합은 알려져 있지 않다.

그래프 이론에서

그래프 이론의 문제에 대한 비구축 알고리즘 증명들은 1988년부터 마이클 펠로우스와 마이클 랭스턴에 의해 연구되었다.[1]

그래프 이론에서 공통적인 질문은 특정 입력 그래프가 특정 속성을 가지고 있는가 하는 것이다.예를 들면 다음과 같다.

입력: 그래프 G.
질문: G의 두 개의 분리 주기가 (사슬의 링크처럼) 위상학적으로 연계되지 않도록 G를 3차원 공간에 삽입할 수 있는가?

3d 공간에 내장된 두 사이클의 연결 여부를 결정하는 매우 지수적인 알고리즘이 있으며, 한 쌍의 사이클을 모두 테스트할 수 있지만, 3d-space에서 가능한 모든 임베딩에 대해 어떻게 설명해야 하는지는 명확하지 않다.따라서 연결성 문제가 해제될 수 있는지 여부는 전혀 명확하지 않다.

그러나 다항식 시간에 연계성이 해제된다는 것을 보여주는 비구축적 증거가 있다.그 증거는 다음과 같은 사실에 의존한다.

  • 답이 "예"인 그래프 집합은 미성년자 수용 시 닫힌다.즉, 그래프 G를 3-d 공간에 연결 없이 삽입할 수 있다면 G의 모든 마이너도 연결 없이 삽입할 수 있다.
  • G와 H 두 그래프에 대해, H가 G의 마이너인지 아닌지를 다항식 시간에 찾을 수 있다.
  • 바이 로버슨-세이모어 정리, 모든 유한 그래프 집합은 유한한 수의 소소수 요소만 포함한다.특히 "예" 인스턴스 세트는 소소수 소소수 요소를 한정적으로 가지고 있다.

입력 그래프 G를 지정하면 다음과 같은 "알고리즘"이 위의 문제를 해결한다.

모든 소소수 요소 H:
만약 H가 G의 미성년자라면, "예"를 반환하라.
"아니오"라고 답례하다

여기서 비건설적인 부분은 로버트슨--시모어 정리.비록 그것이 유한한 수의 마이너 미니멀 요소들이 있다고 보증하지만, 그것은 우리에게 이 요소들이 무엇인지 말해주지 않는다.따라서 위에서 언급한 '알고리즘'을 실제로 실행할 수는 없다.그러나 우리는 알고리즘이 존재하고 그것의 런타임이 다항식이라는 것을 알고 있다.

유사한 방법으로 결정성을 증명할 수 있는 유사한 문제들이 더 많이 있다.어떤 경우에는 다항식 시간에 문제가 증명될 수 있다는 지식이 연구자들을 완전히 다른 방식으로 문제를 해결하는 실제 다항식 시간 알고리즘을 검색하고 찾도록 했다.이것은 비건설적 증거가 건설적인 결과를 가져올 수 있다는 것을 보여준다.[1]

주요 아이디어는 문제를 매개변수로 알 수 없는 집합을 사용하는 알고리즘을 사용하여 해결할 수 있다는 것이다.집합은 알 수 없지만 유한해야 하며, 따라서 다항식 시간 알고리즘이 존재한다는 것을 알고 있다.

비슷한 기법으로 해결할 수 있는 다른 조합 문제도 많다.[2]

알고리즘 계산 중

때로는 주어진 문제에 대한 잠재적 알고리즘의 수가 한정되어 있다.가능한 알고리즘의 수를 셀 수 있고, 한정된 숫자만 "나쁨"임을 증명할 수 있으므로, 적어도 하나의 알고리즘은 "좋음"이어야 한다.

예를 들어 다음과 같은 문제를 생각해 보자.[3]

나는 0과 특정 상수 d 사이의 정수인 n 원소로 구성된 벡터 v를 선택한다.

당신은 "지수 i와 j를 가진 원소의 합이 얼마인가?"라는 형식의 질의인 sum 쿼리를 물어봄으로써 v를 추측해야 한다.합계 쿼리는 1에서 n까지의 모든 수의 지수와 관련될 수 있다.

몇 가지 질문이 필요하십니까?단일 요소의 "sum"을 요청하는 n개의 쿼리를 사용할 수 있기 때문에 n개의 쿼리는 항상 충분하다.그러나 d가 충분히 작을 때 더 잘 할 수 있다.일반적인 생각은 다음과 같다.

모든 쿼리는 요소가 모두 집합 {0,1}에 있는 1 by n 벡터로 나타낼 수 있다.쿼리에 대한 응답은 v에 의한 쿼리 벡터의 도트 곱일 뿐이다. 모든 k 쿼리 세트는 {0,1}에 걸쳐 k-by-n 행렬로 나타낼 수 있으며, 응답 세트는 v에 의한 매트릭스의 곱이다.

매트릭스 M은 v를 고유하게 식별할 수 있다면 "좋음"이다.이는 모든 벡터 v에 대해 제품 M v가 고유하다는 것을 의미한다.M v = M u와 같이 v와 u라는 서로 다른 벡터가 있으면 행렬 M은 "나쁨"이다.

일부 대수학을 사용하면 "나쁜" 행렬의 수를 묶는 것이 가능하다.바운드는 d와 k의 함수다.따라서 충분히 작은 d의 경우, 작은 k를 가진 "좋은" 행렬이 있어야 하며, 이는 식별 문제를 해결하기 위한 효율적인 알고리즘에 해당한다.

이 증거는 두 가지 면에서 비구축적이다: 좋은 매트릭스를 찾는 방법을 알 수 없고, 좋은 매트릭스를 공급하더라도 질의 응답으로부터 벡터를 효율적으로 재구성하는 방법을 알 수 없다.

비슷한 방법으로 해결할 수 있다는 것을 증명할 수 있는 더 많은 유사한 문제들이 있다.[3]

추가 예제

참조

  1. ^ a b Fellows, M. R.; Langston, M. A. (1988). "Nonconstructive tools for proving polynomial-time decidability". Journal of the ACM. 35 (3): 727. doi:10.1145/44483.44491. S2CID 16587284.
  2. ^ Brown, D. J.; Fellows, M. R.; Langston, M. A. (2007). "Polynomial-time self-reducibility: Theoretical motivations and practical results∗". International Journal of Computer Mathematics. 31 (1–2): 1–9. doi:10.1080/00207168908803783.
  3. ^ a b Grebinski, V.; Kucherov, G. (2000). "Optimal Reconstruction of Graphs under the Additive Model" (PDF). Algorithmica. 28: 104–124. doi:10.1007/s004530010033. S2CID 33176053.
  4. ^ Kimmel, S. (2013). "Quantum Adversary (Upper) Bound". Chicago Journal of Theoretical Computer Science. 19: 1–14. arXiv:1101.0797. doi:10.4086/cjtcs.2013.004. S2CID 119264518.

크레딧

이 페이지의 참조는 다음 스택 Exchange 스레드로부터 수집되었다.

참고 항목