P-완전
1. 개요
P-완전은 순차 컴퓨터에서 다룰 수 있는 문제의 복잡도 P와 병렬 컴퓨터에서 다룰 수 있는 문제의 복잡도 NC 간의 관계를 연구하면서 나온 개념으로, NC ≠ P 문제와 관련이 있다. P-완전 문제는 "병렬화할 수 없을 것 같은" 문제의 집합으로, 어떤 P-완전 문제를 빠르게 병렬화하는 방법을 찾는다면 NC ≠ P 명제가 틀리다는 것을 증명하게 된다. 튜링 기계의 작동 여부를 묻는 문제 등이 P-완전 문제로 증명되었으며, 회로 값 문제, 선형계획법 등 다양한 문제가 P-완전에 속한다. 어떤 문제가 P-완전임을 증명하기 위해서는 이미 P-완전으로 알려진 문제를 해당 문제로 환원하는 방법을 사용한다.
-
복잡도 종류 -
P (복잡도)
P는 결정론적 튜링 기계로 다항 시간 내에 풀 수 있는 판정 문제들의 집합이며, 다항 시간 균일 불 대수 회로 집합으로도 정의되고, NP, co-NP 등 다른 복잡도 종류들과 관계를 가진다. -
복잡도 종류 -
P-NP 문제
P-NP 문제는 계산 복잡도 이론에서 P와 NP 복잡도 종류의 관계에 대한 미해결 문제로, 컴퓨터 과학과 수학에 혁명적인 변화를 가져올 것으로 예상되며 암호학, 최적화, 인공지능 등 다양한 분야에 큰 영향을 미칠 수 있다. -
미완성 문단이 포함된 문서 -
나고야시
아이치현에 위치한 나고야시는 아쓰타 신궁을 중심으로 발전하여 오다 노부나가, 도요토미 히데요시, 도쿠가와 이에야스 등의 거점이었으며, 도요타 자동차 중심의 자동차 산업과 MICE 산업 발달, 엑스포 2005 개최, 나고야 의정서 채택 등으로 국제적인 도시로 성장한 16개 구로 구성된 약 230만 명의 인구를 가진 복합적인 도시이다. -
미완성 문단이 포함된 문서 -
진공관
진공관은 진공 상태 용기 내부에 전극을 갖춘 전자 장치로, 다이오드와 트라이오드 발명 후 20세기 중반까지 널리 쓰였으나 트랜지스터 등장으로 사용이 줄었지만, 고주파/고출력 분야나 오디오 앰프 등 특정 분야에서 다양한 종류로 여전히 사용되고 있다.
2. 동기
순차 컴퓨터에서 "다룰 수 있는" 모든 문제를 포함하는 복잡도 [[P]]는 병렬 컴퓨터에서 다룰 수 있는 문제로 구성된 복잡도 [[NC (복잡도)|NC]]를 포함한다. 이는 순차 기계가 병렬 컴퓨터를 시뮬레이트할 수 있기 때문이다. NC = P인지 여부는 아직 밝혀지지 않았다. 다시 말해서, 원래 순차적인, 다룰 수 있는 문제가 존재하는지 여부는 아직 모른다. 다만, P와 [[NP]]가 다를 가능성이 높기 때문에 NC와 P도 다를 것으로 추측한다.
[[NP-완전]]은 "다룰 수 없을 것 같은" 문제들의 집합으로 P = NP 문제를 연구하면서 나온 개념이다. 비슷하게, "병렬화할 수 없을 것 같은", "원래 순차적인 것 같은" 문제의 집합인 P-완전 문제는 NC = P 문제와 관련이 있다. 어떤 P-완전 문제를 빠르게 병렬화하는 방법을 찾는다면, NC ≠ P 명제가 틀리다는 것을 증명하게 된다. 또한, P-완전 문제는 "초대수(polylogarithmic) 공간이 필요한 문제"로 생각할 수도 있다. P-완전 문제에 대한 로그 공간 해법은 [[L (복잡도)|L]] = P를 의미한다.
3. P-완전 문제들
가장 기본적인 P-완전 문제는 튜링 기계와 여기에 들어가는 입력이 하나 있고, 일진수 T가 있을 때, 이 기계가 첫 T 단계 안에 멈출 것인가 하는 문제이다. 이 문제는 P-완전임이 틀림없다. 순차 컴퓨터의 일반적인 시뮬레이션을 병렬화할 수 있다면, 그 컴퓨터에서 돌아가는 어떠한 프로그램도 병렬화할 수 있기 때문이다. 이 문제가 NC라면 P에 들어가는 다른 모든 문제도 NC가 된다. 단계 수가 일진수가 아니라 이진수라면 이 문제는 EXPTIME-완전이 된다.
이는 P-완전 이론에서 흔히 쓰는 방법으로, 어떤 문제를 병렬 컴퓨터가 빨리 풀어내는지는 관심사가 아니다. 다만 병렬 컴퓨터가 그 문제를 순차 컴퓨터보다 훨씬 더 빨리 푸는지만 관심이 있을 뿐이다. 따라서 그 문제를 순차 버전은 P가 되도록 바꾸어 불러야 하며, 이것이 T가 일진수여야 하는 까닭이다.
이밖에도 P-완전임이 증명된, 즉 원래 순차적인 문제는 많이 있다. 이 문제들은 판정 문제 꼴로 되어 있으며, 어떤 문제가 P-완전인지 증명하려면 보통 이미 알고 있는 P-완전 문제를 좋은 병렬 알고리즘을 써서 그 문제로 환산해 본다.
3.1. P-완전으로 증명된 문제
다음은 P-완전으로 증명된 문제들이다.
* 선형계획법: 선형 부등식 제약 조건을 만족하면서 선형 함수를 최대화하는 문제이다.
* 깊이 우선 탐색 순서: 순서가 정해진 인접 리스트로 표현되는 그래프에 마디 u와 v가 있을 때, 깊이 우선 탐색에서 꼭짓점 u를 v보다 먼저 방문하는지를 묻는 문제이다.
* 문맥 자유 문법: 문맥 자유 문법과 문자열 하나가 있을 때, 이 문자열을 그 문법으로 만들 수 있는가?
* 회로 값 문제(CVP): 불리언 회로가 주어지면, 회로의 입력과 회로의 하나의 게이트가 주어지면, 해당 게이트의 출력을 계산한다.
* CVP의 제한된 경우: CVP와 유사하지만, 각 게이트는 두 개의 입력과 두 개의 출력(F와 Not F)을 가지며, 모든 다른 레이어는 AND 게이트이고 나머지는 OR 게이트이다 (또는 동등하게, 모든 게이트는 NAND 게이트 또는 모든 게이트는 NOR 게이트이다). 게이트의 입력은 바로 앞의 레이어에서 가져온다.
* 혼-만족성: 혼 절 집합이 주어지면, 이를 만족하는 변수 할당이 있는가? 이것은 불리언 만족성 문제의 P 버전이다.
* 생명 게임: 콘웨이의 생명 게임의 초기 구성, 특정 셀 및 시간 T (일진법)이 주어지면, 해당 셀이 T 단계 후에 살아 있는가?
* LZW (알고리즘) (1978 패러다임) 데이터 압축: 문자열 s와 t가 주어지면, LZ78 방법으로 s를 압축하면 t가 사전에 추가되는가? ([gzip]]과 같은 LZ77 압축의 경우, 이 문제는 "t가 s에 있는가?"로 축소되므로 훨씬 쉽다.)
* 부분 유형에 대한 유형 추론: 유형 이론에서 람다 계산에서 유형이 지정되지 않은 항이 주어지면, 이 항이 부분 유형을 갖는지 여부를 결정한다.
3.2. P-완전인지 밝혀지지 않은 문제
어떤 문제는 P-완전인지 NC인지 밝혀지지 않았지만, 어려울 것으로 보는 문제들도 있다.
예를 들어 두 이진수의 최대공약수를 찾는 문제의 판정 문제 꼴이나, 확장 유클리드 알고리즘이 이진수 두 개를 입력받았을 때 어떤 답을 할지 판정하는 문제가 있다.