포스테키안

2021 가을호 / HELLO NOBEL

2021-10-19 33

현대 수학의 중심으로, 계산 복잡도 이론  – NP와 P, 그리고 BPP와 P

수학계의 노벨상이라고 불리는 아벨상(Abel Prize)에 대해 혹시 들어본 적이 있나요? 아벨상은 노르웨이 수학자 ‘닐스 헨리크 아벨’의 탄생 200주년을 기리기 위해 노르웨이 정부가 제정해 2003년부터 수여하고 있는 상입니다. 순수수학은 물론 응용수학 분야까지 포함해 일생 동안 쌓아온 업적을 바탕으로 수학자를 매년 선발해 시상하는데요. 올해에는 한 수학자와 컴퓨터 과학자가 아벨상 수상자로 선정되었습니다. 수상자들의 업적 덕분에 이산 수학과 이론 컴퓨터 과학이 현대 수학의 중심에 올라섰다고 하는데요. 그들이 아벨상을 수상할 수 있도록 한 ‘계산 복잡도 이론’에 대해 자세히 알아볼까요?

글. 컴퓨터공학과 오은진 교수님