Deterministic (2) 썸네일형 리스트형 P vs NP 쉽게 이해하기 컴퓨터 과학에는 유명한 난제가 있습니다. 바로 P vs NP입니다. 컴퓨터 과학을 공부하다 보면 언젠간 한 번은 반드시 접하게 되는 흥미롭고도 신기한 문제인데요. 이번 포스트에서는 이에 대해서 함께 알아보도록 하겠습니다. 저는 P vs NP 문제를 대학생 시절 알고리즘 수업을 들을 때 처음 접하였습니다. 솔직히 말씀드리면, 당시에는 진짜 하나도 이해를 못했다고 해도 과언이 아니었습니다. P, NP 내용이 기말고사 범위였는데, 시험 볼 때는 교과서나 강의 자료의 내용을 그저 달달 외워서 베껴 적었던 기억이 나네요. 그 후 대학원 준비를 할 때 P와 NP에 대해서 좀더 알게 되었고, 진학 후에야 그것들을 제대로 이해하는 수준에 이르렀습니다. 그만큼 어렵게 배운 개념이었는데요. 막상 제대로 이해를 한 후에는 .. 야오의 법칙 (Yao's Principle) 이번에는 Yao's principle에 대해서 알아보도록 하겠습니다. 이 글은 이전 포스트에서 이어지는 내용이 많으므로 이를 먼저 읽어 보시는 것을 추천드립니다. 또한 확률에 대한 기본적인 내용을 숙지하셨다는 가정 아래 글이 작성되었다는 점도 밝힙니다. 2019/08/11 - [수학적 도구/Randomness] - Arbitrary & Random Arbitrary & Random 이번 주제는 'arbitrary'와 'random'입니다. 우리말로 번역하면 '임의의 & 무작위의' 정도가 되겠는데 이렇게 제목을 지어버리면 뭔가 제가 의도한 방향대로 읽히지가 않겠더군요. 제목을 영어로 짓기 싫었는데.. gazelle-and-cs.tistory.com 지난 시간 'random'을 설명하기 위해서 같이 고민했던.. 이전 1 다음
