Deterministic vs. Nondeterministic computation

Deterministic vs. Nondeterministic Computation

결정론적 계산과 비결정론적 계산은 계산 이론의 두 가지 근본적인 접근 방식을 나타낸다.
결정론적 계산은 현대 컴퓨터의 기반이 되는 예측 가능하고 명확한 모델을 제공하는 반면, 비결정론적 계산은 이론적으로 더 강력한 계산 모델의 가능성을 탐구한다.

이론적으로는 결정론적 튜링 기계와 비결정론적 튜링 기계가 동일한 문제들을 해결할 수 있지만, 효율성 측면에서는 큰 차이가 있을 수 있다.
P = NP 문제는 이러한 효율성 차이가 본질적인 것인지, 아니면 단지 현재 알고리즘의 한계인지를 묻는 근본적인 질문이다.

현대 컴퓨팅에서는 양자 컴퓨팅, 확률적 알고리즘, 병렬 처리 등을 통해 비결정론적 계산의 일부 장점을 활용하려는 연구가 활발히 진행되고 있으며, 이러한 연구는 복잡한 문제를 더 효율적으로 해결할 수 있는 새로운 가능성을 열어주고 있다.

결정론적 계산(Deterministic Computation)이란 계산 과정의 각 단계에서 다음에 수행할 작업이 현재 상태에 의해 유일하게 결정되는 계산 방식이다. 즉, 주어진 입력에 대해 항상 동일한 경로를 따라 실행되며, 실행 경로가 단 하나만 존재한다.

결정론적 계산 모델에서는 현재 상태와 입력 심볼에 대해 정확히 하나의 다음 상태와 작업만이 존재한다. 다시 말하면 어떤 상태와 입력이 주어지면, 다음에 무엇을 할지가 완전히 정해져 있다. 마치 열차가 정해진 철로를 따라가는 것과 같다.
예를 들어, 최대값 찾기 알고리즘은 항상 같은 최대값을 반환한다.

비결정론적 계산(Nondeterministic Computation)은 계산 과정의 각 단계에서 가능한 다음 작업이 여러 개일 수 있는 계산 방식이다. 즉, 동일한 입력에 대해서도 여러 실행 경로가 존재할 수 있으며, 이론적으로는 이 모든 경로를 동시에 탐색하는 것처럼 작동한다.

비결정론적 계산 모델에서는 현재 상태와 입력 심볼에 대해 여러 가능한 다음 상태와 작업이 존재할 수 있다. 마치 여러 갈래로 나뉘는 길에서 모든 길을 동시에 탐색할 수 있는 능력이 있는 것과 같다.
예를 들어, 리스트에서 무작위로 원소를 선택하고 그것이 최대값인지 확인하는 알고리즘을 들 수 있다.

계산 모델에서의 비교

오토마타 이론과 형식 언어

결정론적 유한 오토마톤(DFA)은 아래와 같은 특징을 가진다.

1. 각 상태에서 각 입력 기호에 대해 정확히 하나의 다음 상태가 존재한다.
2. 현재 상태와 입력에 따라 다음 상태가 유일하게 결정된다.
3. 상태 변화를 위해서는 반드시 입력이 필요하다.
4. 수학적으로 (Q, Σ, δ, q0, F)의 5-튜플로 정의된다.
   결정론적 유한 오토마톤(DFA)에서는 각 상태와 입력 심볼에 대해 정확히 하나의 다음 상태만 존재합니다.
   전이 함수는 δ: Q × Σ → Q로 정의된다.

• Q: 모든 가능한 상태의 집합
• Σ: 입력 알파벳(가능한 모든 입력 심볼의 집합)
• ×: 카티션 곱(두 집합의 모든 가능한 조합)
  현재 상태(Q의 원소)와 입력 심볼(Σ의 원소)의 모든 조합에 대해, 정확히 하나의 다음 상태(Q의 원소)가 결정된다.

비결정론적 유한 오토마톤(NFA)는 다음과 같은 특징을 가진다:

1. 한 상태에서 같은 입력 기호에 대해 여러 개의 가능한 다음 상태가 존재할 수 있다.
2. ε-전이(입력 없이 상태 변화)가 가능하다.
3. 수학적으로 (Q, Σ, s0, δ, F)의 5-튜플로 정의된다.
   비결정론적 유한 오토마톤(NFA)에서는 각 상태와 입력 심볼에 대해 여러 가능한 다음 상태가 존재할 수 있다.
   전이 함수는 δ: Q × Σ → P(Q)로 정의된다(여기서 P(Q)는 Q의 멱집합).

• Q: 모든 가능한 상태의 집합
• Σ: 입력 알파벳(가능한 모든 입력 심볼의 집합)
• ×: 카티션 곱(두 집합의 모든 가능한 조합)
• P(Q): Q의 멱집합(Q의 모든 부분집합의 집합)
  현재 상태와 입력 심볼의 조합에 대해, 가능한 다음 상태들의 집합이 결정된다.

중요한 결과: 모든 NFA는 동등한 DFA로 변환될 수 있다(상태 수는 증가할 수 있음). 따라서 DFA와 NFA는 정규 언어라는 동일한 언어 클래스를 인식합한다.

튜링 기계

결정론적 튜링 기계(DTM)에서는 각 상태와 테이프 심볼에 대해 정확히 하나의 다음 단계(새 상태, 쓸 심볼, 헤드 이동 방향)만 정의된다.
전이 함수는 δ: Q × Γ → Q × Γ × {L, R, S}로 정의된다.

• Q: 모든 가능한 상태의 집합
• Γ: 테이프 알파벳 (테이프에 쓸 수 있는 모든 기호의 집합)
• {L, R, S}: 헤드의 이동 방향 (L: 왼쪽, R: 오른쪽, S: 정지)
  현재 상태와 테이프에서 읽은 기호에 따라, 다음 상태, 테이프에 쓸 새 기호, 그리고 헤드의 이동 방향이 유일하게 결정된다.

비결정론적 튜링 기계(NTM)에서는 각 상태와 테이프 심볼에 대해 여러 가능한 다음 단계가 정의될 수 있다.
전이 함수는 δ: Q × Γ → P(Q × Γ × {L, R, S})로 정의된다.

• Q: 모든 가능한 상태의 집합
• Γ: 테이프 알파벳 (테이프에 쓸 수 있는 모든 기호의 집합)
• {L, R, S}: 헤드의 이동 방향 (L: 왼쪽, R: 오른쪽, S: 정지)
• P(Q × Γ × {L, R, S}): (Q × Γ × {L, R, S})의 멱집합
  현재 상태와 테이프에서 읽은 기호에 따라, 여러 가지 가능한 다음 동작들의 집합이 결정된다.

중요한 결과: 모든 NTM은 동등한 DTM으로 변환될 수 있다. 그러나 이 변환은 실행 시간에 지수적 증가를 가져올 수 있다(즉, NTM이 t 단계에서 문제를 해결하면, 동등한 DTM은 O(2^t) 단계가 필요할 수 있다).

계산 복잡도 이론에서의 비교

복잡도 클래스에서
결정론적 튜링 기계는 P (Polynomial Time) 를 정의하는데 사용된다.
결정론적 튜링 기계에서 다항 시간 내에 해결할 수 있는, 즉 O(n^k)의 시간 복잡도를 갖는 문제들의 집합(여기서 n은 입력 크기, k는 상수).

비결정론적 튜링 기계는 **NP (Nondeterministic Polynomial Time)**를 정의하는데 사용된다.
비결정론적 튜링 기계에서 다항 시간 내에 해결할 수 있는 문제들의 집합이며, 다른 관점에서는, 해답의 정확성을 다항 시간 내에 검증할 수 있는 문제들의 집합으로도 정의된다.

중요한 미해결 문제: P = NP? 이 문제는 “모든 효율적으로 검증 가능한 문제가 효율적으로 해결 가능한가?“를 묻는 컴퓨터 과학의 가장 중요한 미해결 문제 중 하나이다.

다항식 시간 축소(Polynomial-time Reduction)

P와 NP의 관계에서 중요한 개념은 NP-완전성(NP-completeness)이다. NP-완전 문제는 NP에 속하며, NP의 모든 문제가 다항 시간 내에 이 문제로 축소될 수 있는 문제들이다.
이는 만약 어떤 NP-완전 문제에 대한 다항 시간 알고리즘이 발견된다면, P = NP가 증명됨을 의미한다.

실제 구현과 시뮬레이션

1. 결정론적 계산의 구현
   결정론적 계산 모델은 직접적으로 현대 컴퓨터에 구현된다.
   일반적인 프로그래밍 언어(C, Java, Python 등)로 작성된 프로그램은 기본적으로 결정론적이다.
   같은 입력에 대해 항상 동일한 출력을 생성(난수 생성기와 같은 외부 요소가 없다면).

2. 비결정론적 계산의 시뮬레이션
   실제 물리적 컴퓨터는 기본적으로 결정론적이기 때문에, 비결정론적 계산을 직접 구현하는 것은 어렵다.
   비결정론적 계산은 일반적으로 다음과 같은 방식으로 시뮬레이션된다:

   1. 백트래킹(Backtracking): 가능한 모든 경로를 순차적으로 탐색하며, 필요시 이전 결정 지점으로 돌아가 다른 경로를 탐색.
   2. 병렬 처리(Parallel Processing): 여러 처리 단위가 각각 다른 실행 경로를 동시에 탐색.
   3. 확률적 알고리즘(Probabilistic Algorithms): 무작위성을 활용하여 가능한 경로 중 하나를 선택.

결정론적 vs. 비결정론적 계산 과정에서의 차이

두 접근 방식의 핵심 차이는 계산 과정에서 선택지와 경로를 처리하는 방식에 있다.

미로 찾기 예시

미로를 통과하는 문제를 생각해 보면:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

S ###########
# #       # #
# # ##### # #
# #     # # #
# ##### # # #
#       # # #
######### # #
#         # #
# ######### #
#           E
#############

여기서 S는 시작점, E는 출구.

결정론적 접근

결정론적 알고리즘(예: 깊이 우선 탐색)은 다음과 같이 작동한다:

1. 현재 위치에서 가능한 이동 방향(위, 아래, 왼쪽, 오른쪽)을 확인한다.
2. 미리 정해진 우선순위(예: 오른쪽→아래→왼쪽→위)에 따라 한 방향을 선택한다.
3. 선택한 방향으로 이동한다.
4. 막다른 길에 도달하면 이전 교차점으로 돌아가 다른 방향을 시도한다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def dfs_maze(maze, start, end):
    stack = [start]
    visited = set([start])
    
    while stack:
        current = stack.pop()  # 한 번에 하나의 경로만 탐색
        
        if current == end:
            return True  # 출구 발견
        
        # 가능한 모든 이동 방향 확인
        for neighbor in get_neighbors(current, maze):
            if neighbor not in visited:
                visited.add(neighbor)
                stack.append(neighbor)
    
    return False  # 출구를 찾을 수 없음

이 알고리즘은 한 번에 하나의 경로만 탐색하며, 필요한 경우 백트래킹(다시 되돌아가기)을 수행한다.

비결정론적 접근

비결정론적 알고리즘은 이론적으로 다음과 같이 작동할 수 있다:

1. 현재 위치에서 가능한 모든 이동 방향을 동시에 시도한다.
2. 각 방향으로 동시에 탐색을 계속한다.
3. 어느 하나라도 출구에 도달하면 성공이다.

이를 의사 코드로 표현하면:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

function nondeterministic_solve_maze(maze, position):
    if position is exit:
        return SUCCESS
    
    // 다음과 같은 "마법의" 연산자가 있다고 가정
    direction = CHOOSE(up, down, left, right)
    
    new_position = move(position, direction)
    if new_position is valid:
        return nondeterministic_solve_maze(maze, new_position)
    else:
        return FAIL

여기서 CHOOSE 연산자는 모든 가능한 선택을 동시에 시도한다고 가정한다.
실제로는 이런 마법의 연산자는 존재하지 않으므로, 실제 구현에서는 백트래킹이나 병렬 처리를 통해 시뮬레이션해야 한다.

문자열 수용 예시: 정규 표현식 일치

정규 표현식 일치 문제를 생각해 봅시다. 다음 정규 표현식이 주어졌다고 가정하면:

1

a(b|c)*d

이 표현식은 ‘a’로 시작하고, ’d’로 끝나며, 중간에 ‘b’와 ‘c’가 0번 이상 반복되는 문자열과 일치한다.

결정론적 접근 (DFA)

결정론적 유한 오토마톤(DFA)으로 구현하면:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

상태 0: 시작 상태
상태 1: 'a'를 읽은 후
상태 2: 'b' 또는 'c'를 읽은 후
상태 3: 'd'를 읽은 후 (종료 상태)

전이 함수:
δ(0, 'a') = 1
δ(1, 'b') = 2
δ(1, 'c') = 2
δ(1, 'd') = 3
δ(2, 'b') = 2
δ(2, 'c') = 2
δ(2, 'd') = 3

이 DFA는 항상 정확히 하나의 경로를 따라 상태를 전이한다.

비결정론적 접근 (NFA)

비결정론적 유한 오토마톤(NFA)으로 구현하면:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

상태 0: 시작 상태
상태 1: 'a'를 읽은 후
상태 2: 'b' 또는 'c'를 읽은 후
상태 3: 'd'를 읽은 후 (종료 상태)

전이 함수:
δ(0, 'a') = {1}
δ(1, 'b') = {1, 2}  // 'b'를 읽고 상태 1 또는 2로 갈 수 있음
δ(1, 'c') = {1, 2}  // 'c'를 읽고 상태 1 또는 2로 갈 수 있음
δ(1, 'd') = {3}
δ(2, 'b') = {2}
δ(2, 'c') = {2}
δ(2, 'd') = {3}

NFA는 “마법적으로” 여러 상태에 동시에 있을 수 있다.
어떤 경로든 종료 상태에 도달하면 문자열이 수용된다.

계산 복잡도 예시: SAT 문제

Boolean 만족가능성 문제(SAT)를 생각해 보면.

이 문제는 주어진 Boolean 식이 참이 되도록 하는 변수 할당이 존재하는지 확인하는 문제이다.
예: (x₁ ∨ x₂) ∧ (¬x₁ ∨ x₃) ∧ (¬x₂ ∨ ¬x₃)

결정론적 접근

결정론적 알고리즘은 모든 가능한 변수 할당을 하나씩 시도해야 한다:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def solve_sat_deterministic(formula, variables):
    if len(variables) == 0:
        return evaluate(formula, {})  # 모든 변수가 할당됐는지 확인
    
    var = variables[0]
    remaining_vars = variables[1:]
    
    # var를 True로 설정하고 재귀적으로 시도
    assignment = {var: True}
    if solve_sat_deterministic(formula, remaining_vars):
        return True
    
    # var를 False로 설정하고 재귀적으로 시도
    assignment = {var: False}
    return solve_sat_deterministic(formula, remaining_vars)

이 접근법은 모든 가능한 할당(2^n개, n은 변수 수)을 순차적으로 시도한다.

비결정론적 접근

비결정론적 튜링 기계는 다음과 같이 작동할 수 있다:

1. 각 변수에 대해 True 또는 False 값을 “비결정론적으로 선택"한다.
2. 이 할당으로 공식을 평가한다.
3. 공식이 참이면 “예"를 반환하고, 그렇지 않으면 “아니오"를 반환한다.

의사 코드로 표현하면:

1
2
3
4
5
6
7
8
9

function nondeterministic_solve_sat(formula, variables):
    assignment = {}
    for each var in variables:
        assignment[var] = CHOOSE(True, False)  // 비결정론적 선택
    
    if evaluate(formula, assignment):
        return YES
    else:
        return NO

이론적으로 비결정론적 기계는 단 한 번의 “마법적인 추측"으로 정답을 찾을 수 있다. 이것이 SAT 문제가 NP 클래스에 속하는 이유이다.

장단점 분석

결정론적 계산의 장단점

장점:

• 예측 가능성과 재현성이 높음
• 디버깅이 상대적으로 용이함
• 직접적인 하드웨어 구현이 가능함
• 시간 및 공간 복잡도 분석이 명확함

단점:

• 일부 문제에서는 효율적인 해결책을 찾기 어려움
• 복잡한 탐색 공간에서 최적해를 찾는 데 비효율적일 수 있음
• 병렬화가 제한적일 수 있음

비결정론적 계산의 장단점

장점:

• 이론적으로 특정 문제에서 더 효율적인 해결책을 제공할 수 있음
• 복잡한 탐색 공간에서 최적해를 더 빠르게 찾을 수 있는 이론적 가능성
• 본질적으로 병렬화에 적합함

단점:

• 실제 구현이 어려움
• 결과의 재현성이 낮을 수 있음
• 시뮬레이션 시 자원 소모가 큼
• 디버깅이 복잡함

응용 분야

결정론적 계산의 응용

• 일상적인 컴퓨터 프로그램과 알고리즘
• 데이터베이스 시스템
• 운영 체제
• 실시간 제어 시스템
• 금융 거래 시스템

비결정론적 계산의 응용

• 인공지능과 기계 학습
• 최적화 문제 해결
• 자연어 처리
• 게임 이론
• 양자 컴퓨팅(양자 시스템은 본질적으로 비결정론적 특성을 갖음)

현대적 발전과 연구 동향

1. 양자 컴퓨팅(Quantum Computing)
   양자 컴퓨팅은 양자 역학적 현상을 이용하여 특정 문제를 효율적으로 해결할 수 있는 가능성을 제공합니다. 양자 컴퓨터는 양자 중첩과 얽힘을 통해 특정 연산을 병렬로 수행할 수 있으며, 이는 비결정론적 계산의 일종으로 볼 수 있습니다.

2. 확률적 알고리즘(Probabilistic Algorithms)
   확률적 알고리즘은 무작위성을 활용하여 결정론적 알고리즘보다 더 효율적으로 문제를 해결할 수 있는 가능성을 제공한다. 예를 들어, 몬테카를로 알고리즘은 무작위 샘플링을 통해 복잡한 수학적 문제의 근사 해를 효율적으로 찾을 수 있다.

3. 병렬 및 분산 컴퓨팅(Parallel and Distributed Computing)
   현대의 병렬 및 분산 컴퓨팅 시스템은 비결정론적 계산의 일부 장점을 활용하려는 시도이다.
   여러 계산 단위가 동시에 서로 다른 실행 경로를 탐색함으로써 특정 문제에 대한 해결 시간을 단축할 수 있다.

비교 요약표

참고 및 출처