Post Correspondence Problem 문서 원본 보기

[[분류:계산 이론 개론]]
[[분류:컴퓨터 공학]]
상위 문서: [[Turing Machines/Post Correspondence Problem|Turing Machines]]

==개요==
해당 문서에서는 Post Correspondence Problem(PCP)에 대해서 설명한다.

==Definition of PCP==
PCP는 도미노 개념에 기반하여 조직된 문제이다. 도미노란 아래와 같은 “위 문자열(top string)”과 “아래 문자열(bottom string)” 쌍을 의미한다:
 <math>[\frac{b}{ca}]</math>: 위 문자열은  "b", 아래 문자열은 "ca"
PCP는 도미노를 원하는 순서로 반복을 허용하여 나열했을 때, 위 문자열 전체가 아래 문자열 전체와 같은지(매치되는지) 확인하는 문제이다. 예를 들어:
 <math>[\frac{a}{ab}], [\frac{b}{ca}], [\frac{ca}{a}], [\frac{a}{ab}], [\frac{abc}{c}]</math>
와 같은 도미노의 나열은 위, 아래 문자열이 "abcaaabc"로 같기 때문에 "매치(match)가 존재한다"가 문제의 답이다.

===PCP Formulation as a Language===
PCP의 [[NP-Completeness#Problems|인스턴스]]는 도미노들의 리스트이며, 아래와 같이 나타내어 진다:
 <math>P=\{[\frac{t_1}{b_1}], \frac{t_2}{b_2}], \cdots, \frac{t_n}{b_n}]\}</math>
이때, 위와 같은 인스턴스를 문자열로 [[Turing Machines#Encoding Objects as Strings|인코딩]]한 것은 <math>\langle P \rangle</math>과 같이 나타내어진다. 이러한 정의를 통해 PCP를 언어로 정의하면 아래와 같다:
 PCP <math>= \{\langle P \rangle|P</math>는 매치가 존재하는 PCP 인스턴스이다.<math>\}</math>
이때, 위 튜링머신은 undecidable하다.
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>

==각주==