[계산이론](25)[reducibility]

reducibility

• reduction: A문제를 B문제로 바꿔 풀어보자
  그리고 B문제를 풀 수 있는 방법이 있다면,
  그 방법으로 A도 풀 수 있을 것이다!
  예) 곱셈은 덧셈 여러번으로 reduce될 수 있다.
      곱셈 -(reduce)-> 덧셈
      (sol) <----------- (sol)
• A is reducible to B: A가 B로 reduce될 수 있음
  A ≤ B의 관계

A가 B로 reduce 될 수 있고, B가 deciable하면 -> A도 decidable하다.
    A가 B로 reduce 될 수 있고, A가 undicidable이면 -> B도 undecidable하다.
즉, 알려진 문제 -> 새 문제 일때,
새 문제는 적어도 알려진 문제보다 같거나 더 어렵다.

 

예시

• reduction은 복잡도 이론에서도 쓰임!
• undecidable의 증명
  이미 알려진 undeciable문제 A가 새로운 문제 B로 reduce될 수 있는지만 보면 됨.

ATM is undecidable

이전에 halting problem을 증명할 때는 그냥 halt 자체에서 모순을 끌어냈음
그러나 ATM과의 관계를 통해서 ATM도 증명 가능함
(물론 전공책에선 ATM을 증명하고 halt를 증명하긴 했다...)

 

A_TM과 halting problem은 서로 reduce할 수 있다.

• halt -> A_TM
  만약 TM_HALT H를 가지고 있다면,
  A_TM을 input <M, w>에 대해
      1. 먼저 H에서 멈추지 않는 경우를 모두 reject한다
      2. 그 다음 <M, w>를 시뮬레이션 해서 accept, reject를 판정한다 
  이와 같은 방식으로 만들 수 있으므로, H가 존재하면 A_TM도 존재한다.
• A_TM -> halt
  만약 A_TM S를 가지고 있다면,
  TM_HALT를 input <M, w>에 대해
      1. M이 accept or reject로 갈 때 억지로 accept로 가게 M'로 개조
      2. S에 M'을 넣어 accept하면 원본 M은 accept or reject로 멈추는 것이고, 만약 accept를 안하면 loop에 빠진 것이라 판단하면 된다.
  이와 같은 방식으로 TM_HALT를 만들 수 있으므로, S가 존재하면 TM_HALT도 존재한다.

따라서 halting problem을 증명하는 것은 A_TM을 증명하는 것이고,
A_TM을 증명하는 것은 halting problem을 증명하는 것이다.

 

따라서
HALT is reducible to ATM & HALT is undecidable
-> ATM is undecidable