결정가능성 decidability
- 결정 문제: 참/거짓으로 답할 수 있는 문제
- 예: 정지 문제(halting problem): 어떤 프로그램이 정지할지/무한루프에 빠질지 예측하는 문제
- 결정가능성: 어떤 결정 문제에서 올바른 답을 도출하는 유한한 단계의 알고리즘이 존재하는가?
- 정지 문제는 결정 불가능(즉, 어떤 프로그램이 언젠가 멈출지 알아내는 일반적 방법은 없음)
- 명제 논리는 결정 가능
- 1차 술어 논리는 결정 불가능
- 실용적으로 문제가 됨: 어떤 종류의 질문을 던지면 영원히 답을 얻지 못할 수 있음
- 심지어 결정가능하더라도 계산이 너무 오래 걸리면 실용적이지 못함(→계산복잡도)
- 현실적인 추론 시스템은 1차 술어 논리를 제한
- 표현할 수 있는 의미나 추론할 수 있는 능력이 한정됨
- 대신 결정가능하고(예/아니오로 대답 가능), 계산복잡도도 낮아짐(빨리 돌아감)
다양한 추론 시스템
- Prolog
- 1차 술어논리를 제한하고 변형한 논리 프로그래밍 언어
- 증명에 실패하면 참(negation as failure) → 닫힌 세계 가정(Closed World Assumption)
- Backward chaining을 이용해 주어진 질문에 답변
- 종료 보장 X
- Datalog
- Prolog를 더 제한하여, 데이터베이스에서 규칙을 적용하여 사실들을 도출하기 위한 용도
- 종료 보장
- Kanren
- 주어진 관계를 만족하는 값을 탐색하기 위한 작은 언어
- 복잡한 구조적 질문도 답할 수 있음
- 종료 보장 X
계산 복잡도
- 결정가능하더라도 답이 나오는데 시간이 너무 오래 걸리면 현실적으로 의미가 없음
- 계산 복잡도: 문제의 크기와 문제를 푸는데 걸리는 시간의 관계
- 빅 O 표기법: 문제의 복잡도가 특정 함수보다 빨리 증가하지 않음
- 예:
O(n!)이면 이차함수보다 빨리 증가하지는 않는다는 뜻
- 다항 시간: 문제를 푸는데 걸리는 시간을 다항식(예: n, n^2, n^3 등)으로 표현할 수 있음
- 교과서적인 행렬의 곱셈
O(n^3)
- 현재 가장 빠른 행렬 곱셈 알고리즘
O(n^2.371866)
- 계산복잡도가 낮아야 큰 문제를 현실적으로 다룰 수 있음
계산 복잡도 클래스
- P: 다항시간 안에 풀 수 있는 결정문제
- NP: 힌트가 있거나 잘 찍으면 다항 시간 안에 풀 수 있는 결정문제
- 반대로 말하면 다항 시간 안에 문제를 풀지는 못해도, 정답은 확인할 수 있음
- 상대적으로 빨리 '검증'할 수 있음
- 모든 P 문제는 NP 문제이기도 함(다항 시간에 풀 수 있으면 정답도 확인할 수 있으므로)
- NP가 아닌 문제도 있음: 답을 줘도 정답인지 확인하는데 오래 걸리는 문제들
- NP 난해(hard): 모든 NP 문제를 다항 시간 안에 이 문제로 바뀔 수 있는 경우
- 이 자체는 P, NP, 그 이상 어느 것도 될 수 있음
- NP 완전(complete): NP 난해인 NP 문제
- 모든 NP 문제를 다항 시간 안에 이 문제로 바꿀 수 있음
- 이 문제 자체는 정답은 다항 시간 안에 확인할 수 있음
P-NP 문제
- P = NP인가, 아니면 P≠NP인가?
- 또는 NP 완전 문제를 다항시간 안에 풀 수 있는 알고리즘이 있는가?
- 상금 100만 달러가 걸린 밀레니엄 문제 중에 하나
- 현행 암호 체계는 NP 문제(소인수분해)를 이용하므로, P = NP를 증명하면 타격을 받을 수 있음
