-
NP-Complete 게임들과 그 증명
안녕하세요? 우리가 여가 시간에 많이 즐기는 친숙한 여러 게임들, 가령 루빅스 큐브(의 최단거리 찾기), 스도쿠와 같은 고전적인 게임들부터 지뢰찾기, 테트리스, 솔리테어, 팩맨, 슈퍼 마리오, 캔디 크러쉬 사가, 2048, 루빅스 큐브, 쿠키 클리커 등과 같은 게임은 NP-Complete 문제임이 증명되어 있습니다. 이번 글에서는 이러한 게임들을 어떠한 decision problem으로 정의하면, 이러한 문제들이 NP-Complete가 되고 이를 어떻게 증명할지에 대해 알아보겠습니다. P 문제와 NP 문제 P와 NP, 그리고 NP-Hard와 NP-Complete가 어떠한 것인지는 널리 잘 알려져 있습니다. 멤버십 블로그에서도 기존에 이와...
-
대화형 증명 시스템과 영지식 증명
이전 글에서는 공개 키 암호화 시스템에서 보안을 어떻게 챙겨야 하는가를 다루었습니다. 암호화 알고리즘은 기본적으로 외부의 개입이 없습니다. 그러나 세상에는 다양한 프로토콜이 있고, 둘 이상이 통신하며 내용을 주고 받습니다. 이 글에서는 프로토콜의 보안을 어떻게 챙기고 또 암호화폐로 인해 널리 알려진 속성인 영지식성zero-knowledgeness을 다루고자 합니다. 대화형 증명 시스템 NP Revisited Arthur-Merlin Protocol IP 영지식 알리바바와 동굴 Indistinguishability Revisited Fiat-Shamir Protocol Hamiltonian Cycle 마무리 각주 대화형 증명 시스템 대화형 증명 시스템interactive proof system은 두 개체 증명자prover와 검증자verifier로 이루어져...
-
COVID-19 확산의 분석
COVID-19 확산의 분석 Contents 개요 및 기존 분석들 분석 방향성 분석 결과 및 의의 이후 방향성 참고 개요 및 기존 분석들 COVID-19 사태는 현재 인류에 큰 피해를 주고 있으며, 앞으로 얼마나 더 지속될지 모르고, 후에 유사한 전염병이 다시 나타났을 때, 좀 더 유연하고 의미있는 해결책과 대비책이 존재하면 좋을 것이라고 생각했습니다. 또한 코로나와 같은 사회 경제에 직접적으로 영향을 주게 되는 경우, 어떤 패턴이 존재하고 변화하는지를 알아보는 과정이 흥미로울 것 같아서 분석을 진행해보게 되었습니다. 먼저, 기존의 분석에...
-
Dynamic MSF with Subpolynomial Worst-case Update Time (Part 1)
Dynamic MSF with Subpolynomial Worst-case Update Time (Part 1) 그래프에서 최소 스패닝 트리 (Minimum spanning tree)를 구하는 문제는 아주 잘 알려져 있고, 일반적으로 가장 처음 공부하게 되는 그래프 알고리즘에 속하며, 매우 다양한 개념에 응용된다. 그래프의 최소 스패닝 트리는 크루스칼 알고리즘을 통해서 $O(m \log m)$ 에 효율적으로 구할 수 있다. 하지만 그래프에서 간선이 추가되고 제거되는 등의 업데이트가 가해진다면, 이 알고리즘은 매 갱신마다 전체 간선 리스트를 전부 순회해야 하니 더 이상 효율적이지 않게 된다. 이렇게 그래프의 일부가...
-
Codeforces Round #688 개최 후기
개요 Codeforces Round #688 (Div. 2) Announcement Editorial (이전 글) Codeforces Round #620 개최 후기 (이전 글) Codeforces Round #578 개최 후기 올해 초 Codforces에서 개최했던 620번 라운드는 제게는 잊을 수 없는 기분 좋은 추억입니다. 처음으로 단독 출제자를 해본 대회에 무려 14612명이 등록해서 좋은 반응을 이끌어냈었다는 것이 정말 좋았습니다. 그 기분을 다시 느끼고 싶어서 라운드가 종료되고 얼마 지나지 않아 바로 다음 라운드를 준비하기 시작했고,1 12월 4일 22시 05분(KST)부터 2시간 15분에 걸쳐 Codeforces Round #688 (Div....