코브햄의 논문

Cobham's thesis
코브햄의 정리와 혼동하지 않기 위해서입니다.

코브햄-에드몬드 논문(앨런 코브햄과 잭 에드몬드의 이름을 딴 이름)으로도 알려진 코브햄의 논문은 계산 문제가 다항식 시간에 계산될 수 있는 경우에만, 즉 복잡도 등급 P에 놓여 있는 경우에만 어떤 계산 장치에서 타당하게 계산될 수 있다고 주장한다.[1][2][3][4]현대적인 용어로, 복잡도 등급 P의 다루기 쉬운 문제를 식별한다.

형식적으로 다항식 시간에 문제를 해결할 수 있다고 말하는 것은 문제의 n비트 인스턴스를 입력으로 하여 시간 O(nc)에 해답을 산출할 수 있는 알고리즘이 존재한다고 말하는 것이다, 문자 O는 빅 O 표기법이고 c는 문제의 특정 사례가 아닌 문제에 따라 달라지는 상수다.

앨런 코브햄의 1965년 논문 '함수의 본질적인 계산 곤란'[5]은 다항식 시간에 해독 가능한 문제들로 구성된 복잡도 등급 P의 개념을 가장 먼저 언급한 것 중 하나이다.코브햄은 이 복잡성 등급이 실현 가능한 계산 가능한 문제들의 집합을 설명하는 좋은 방법이라고 이론화했다.

잭 에드먼즈의 1965년 논문 '길, 나무, 꽃'[6]도 P를 다루기 쉬운 문제로 식별한 공로로 인정받고 있다.[7]

제한 사항

그래프는 933MHz Pentium III 컴퓨터(평균 100개 인스턴스, 데이터)를 사용하여 최신 전문 알고리즘으로 해결한 배낭 문제에 대한 문제 해결 시간을 밀리초(밀리초) 대 n으로 나타낸다.[8]이차 방정식의 적합을 통해 이론상 기하급수적인 최악의 경우 복잡성 추정치가 있음에도 불구하고 50–10,000개의 변수를 가진 인스턴스들의 경험적 알고리즘 복잡성은 O(log n)2임을 알 수 있다.

코브햄의 논문은 계산 복잡성 이론의 전개에 있어 중요한 이정표지만, 알고리즘의 실용성에 적용되는 한계도 있다.논문은 본질적으로 'P'는 '쉽고 빠르고 실용적'을 의미하며, 'P'는 '힘들고 느리고 비실용적'을 의미한다.그러나 논문이 실제 런타임에 영향을 미치는 몇 가지 중요한 변수를 추상화하기 때문에 이것이 항상 사실인 것은 아니다.

  • 일정한 요인과 저차 항을 무시한다.
  • 그것은 지수의 크기를 무시한다.시간 계층 구조 정리는 임의적으로 큰 지수를 요구하는 P에 문제의 존재를 증명한다.
  • 입력의 일반적인 크기를 무시한다.

세 가지 모두 관련성이 있고, 알고리즘 분석에 대한 일반적인 불만사항이지만, 코브햄의 논문은 실용성에 대해 명시적으로 주장하기 때문에 특히 적용된다.카범:영국의 순교자의 논문에 의하면 한 문제에 대한 최선의 알고리즘이 가능한 일로 여겨지고 20.00001 n지시를 받아들이는 알고리즘에 문제가 infeasible—even는 반면 크기 n의 문제의 인스턴스)106w. 해결될 수 있을 것 한 nx2전 알고리듬, 크기의 인스턴스를 결코 풀지 못할 수 있n200 지시를 받아들이ithout 연락Iculty. 실제 문제가 수백만 개의 변수(예: 운영 연구 또는 전자 설계 자동화)를 갖는 분야에서는 O(n3) 알고리즘도 비현실적인 경우가 많다.[9]

별도의 고려사항은 정확한 해결책을 찾을 수 없는 경우 대부분 대략적인 해결책에 만족한다는 것이다.예를 들어, 여행 판매원 문제는 다항 시간(NP-완전)에 정확히 해결할 수 없는 것으로 널리 의심되지만, 다항 시간에는 크리스토피데스 알고리즘과 같은 방법으로 좋은 해결책을 얻을 수 있다.

참조

  1. ^ Oded Goldreich (2008), Computational complexity: a conceptual perspective, Cambridge University Press, p. 128, ISBN 978-0-521-88473-0
  2. ^ Dexter Kozen (2006), Theory of computation, Birkhäuser, p. 4, ISBN 978-1-84628-297-3
  3. ^ Egon Börger (1989), Computability, complexity, logic, Elsevier, p. 225, ISBN 978-0-444-87406-1
  4. ^ Homer, Steven; Selman, Alan L. (1992), "Complexity Theory", in Kent, Alan; Williams, James G. (eds.), Encyclopedia of Computer Science and Technology, vol. 26, CRC Press
  5. ^ Alan Cobham (1965), The intrinsic computational difficulty of functions (PDF)
  6. ^ Edmonds, Jack (1965). "Paths, trees, and flowers". Can. J. Math. 17: 449–467. doi:10.4153/CJM-1965-045-4.
  7. ^ Meurant, Gerard (2014). Algorithms and Complexity. p. p. 4. ISBN 978-0-08093391-7. A problem is said to be feasible if it can be solved in polynomial time (as stated for the first time in Edmonds [26] [1965, Paths, trees, and flowers])).
  8. ^ D. Pinger, 2003."힘든 배낭 문제는 어디에 있지?"기술 보고서 2003/08, 덴마크 코펜하겐 코펜하겐 대학 컴퓨터 과학부, 2015년 1월 31일에 접속한 [1] 웨이백 기계에 보관된 2015-11-23을 참조하십시오.
  9. ^ Rotman, Brian (18 June 2003). "Will the digital computer transform classical mathematics?". Phil. Trans. R. Soc. Lond. A. 361 (1809): 1675–1690. doi:10.1098/rsta.2003.1230. PMID 12952680.