(2021.12.01) 알고리즘 수업 들으면서 정리하기 23탄 w14 실강 NP-completeness 내용 시작 계산 복잡도, 튜링 기계에 대해 배웠다 NP-completeness Computational Complexity > 알고리즘은 특정 알고리즘의 performance 특성 (성능 특성)에 대한 연구이다. > 계산 복잡도(계산 이론)은 알고리즘보다는 문제의 특성에 대한 연구이다. 우리는 문제를 solvable problem과 unsolvable problem으로 나눌 수 있다. > unsolvable problem은 다시 세가지로 나뉜다. 1. Unsolvable problems ---> halting problem 2. Solvable problems a. Provably intractable..