차이점
이 페이지의 선택한 이전 버전과 현재 버전 사이의 차이점을 보여줍니다.
|
복잡도종류 [2011-09-05 06:57] lifthrasiir 옛 풉;에서 복사 및 수정 |
복잡도종류 [2011-09-05 07:08] (현재) lifthrasiir P!=NP라는 조건을 빼먹고 있었는데 그냥 쓸데 없는 부분을 삭제해서 해결 |
||
|---|---|---|---|
| 줄 3: | 줄 3: | ||
| Complexity class. [[전산학]]에서 다루는 문제의 종류를 그 복잡도에 따라 분류한 집합. [[알고리즘분석]]과 [[계산이론]]의 주된 주제 중 하나이다. | Complexity class. [[전산학]]에서 다루는 문제의 종류를 그 복잡도에 따라 분류한 집합. [[알고리즘분석]]과 [[계산이론]]의 주된 주제 중 하나이다. | ||
| - | 여기서 말하는 "복잡도"라는 것은 매우 잘 정의된 개념으로, 어떤 문제의 복잡도는 그 문제를 특정한 종류의 [[계산모델]]로 풀 때 필요한 시간이나 공간을 가지고 결정된다. 예를 들어 [[외판원문제]](TSP)의 [[결정문제]] 버전은 [[결정적튜링기계]]에서는 아무리 용을 써도 입력 크기의 [[다항식]]에 비례하는 시간([[다항시간]]) 안에 문제를 풀 수 없는 반면, [[비결정적튜링기계]]에서는 가능하다. 이를 복잡도 종류를 사용해서 표현하면 $$\mathrm{TSP} \notin \mathbf{P}$$지만 $$\mathrm{TSP} \in \mathbf{NP}$$라고 표현할 수 있다. 문제의 복잡도를 이런 식으로 분류하는 것은 여러 가지로 중요한데 이를테면 어떤 문제는 좀 더 단순한 (추상) 기계만으로 풀 수 있거나 훨씬 효율적으로 풀수 있다거나 하는 특성이 있기 때문이다. | + | 여기서 말하는 "복잡도"라는 것은 매우 잘 정의된 개념으로, 어떤 문제의 복잡도는 그 문제를 특정한 종류의 [[계산모델]]로 풀 때 필요한 시간이나 공간을 가지고 결정된다. 예를 들어 [[외판원문제]](TSP)의 [[결정문제]] 버전은 [[비결정적튜링기계]]에서는 입력 크기의 [[다항식]]에 비례하는 시간([[다항시간]]) 안에 문제를 풀 수 있다는 게 알려져 있으며, 이를 복잡도 종류를 사용해서 표현하면 $$\mathrm{TSP} \in \mathbf{NP}$$라고 표현할 수 있다. 문제의 복잡도를 이런 식으로 분류하는 것은 여러 가지로 중요한데 이를테면 어떤 문제는 좀 더 단순한 (추상) 기계만으로 풀 수 있거나 훨씬 효율적으로 풀수 있다거나 하는 특성이 있기 때문이다. |
| 전산학이나 [[프로그래밍]]을 하면서 볼 수 있는 대다수의 구체적인(([[인공지능]]같이 문제의 성격 자체가 구체적일 수 없는 경우를 빼고)) 문제들은 [[NP복잡도]]에 속하며, 그 중 많은 수가 [[P복잡도]]에 속한다는 것이 알려져 있다. (그러나 나머지가 정말로 P에 속하지 않는 건지는 아직 풀리지 않았다. [[P=NP]] 문제 참조.) [[촘스키위계]]와 같은 [[형식언어]]도 복잡도로 표현할 수 있다. | 전산학이나 [[프로그래밍]]을 하면서 볼 수 있는 대다수의 구체적인(([[인공지능]]같이 문제의 성격 자체가 구체적일 수 없는 경우를 빼고)) 문제들은 [[NP복잡도]]에 속하며, 그 중 많은 수가 [[P복잡도]]에 속한다는 것이 알려져 있다. (그러나 나머지가 정말로 P에 속하지 않는 건지는 아직 풀리지 않았다. [[P=NP]] 문제 참조.) [[촘스키위계]]와 같은 [[형식언어]]도 복잡도로 표현할 수 있다. | ||
저작권자 © 1999–2012 강 성훈. 저작권을 약간 가집니다. | 풉;이 뭐냐고요?