-
#P-완전성, 그리고 완전 매칭의 개수
이 글은 튜링 기계와 NP-complete에 대한 기본 배경지식을 전제로 합니다. 서론 이분 그래프가 주어졌을 때 최대 매칭을 구하는 문제는 알고리즘 문제 풀이에서 잘 알려져 있습니다. 심지어 일반적인 그래프가 주어져도 최대 매칭을 다항 시간에 구할 수 있습니다. 그러므로 완전 매칭이 존재하는지도 같은 방법으로 구할 수 있습니다. 하지만 완전 매칭의 개수를 구하라고 하면 어떻게 될까요? 카운팅 문제와 #P-완전 NP-완전성을 이야기할 때는 문제가 결정 문제로 한정됩니다. 예를 들어 최대 클릭 문제는 “가장 큰 클릭은 무엇인가?”가 아니라 “크기가 $k$...
-
Dynamic MSF with Subpolynomial Worst-case Update Time (Part 2)
Dynamic MSF with Subpolynomial Worst-case Update Time (Part 2) Chapter 3. Continued Proof of Lemma 3.4: The Algorithm. $G_0, \alpha_0, l$ 을 Lemma 3.4의 입력이라고 하자. 알고리즘은 $l + 1$ 개의 레벨 로 그래프를 관리한다. 각 레벨은 간선의 부분집합을 관리하며, one-shot expander pruning algorithm을 호출한다. 레벨이 깊을 수록 (숫자가 클 수록) one-shot expander pruning algorithm의 호출 횟수는 많아지며, 반대로 간선의 개수는 적어진다. 정확히 어떠한 원리인지는 후술하고, 아래 필요한 정의를 나열한다. $\delta = \frac{2}{l}$ 이다. $n,...
-
Pytorch lightning 튜토리얼
소개 Pytorch Lightning은 Pytorch에 대한 High level의 인터페이스를 제공하기 위한 라이브러리입니다. 이 라이브러리는 모델 코드와 엔지니어링 코드를 분리해서 코드를 깔끔하게 만들 수 있도록 해주고 16-bit training, 다중 gpu 사용 등을 포함한 다양한 학습 기법을 몇 줄의 코드로 손쉽게 사용할 수 있도록 합니다. 이번 글에서는 pytorch lighting으로 MNIST 데이터 셋에 대한 분류 모델을 구현하면서 전반적인 라이브러리의 사용법에 대해 알아보겠습니다. 글에서 사용된 전체 코드는 여기에서 확인할 수 있습니다. Lightning Module 구현하기 Pytorch lightning에서는 trainer와 모델이 상호작용을 할...
-
SABER: Mod-LWR based KEM
1. Introduction 저번 글에서는 양자 컴퓨터와 Post Quantum Cryptography에 대해 다루었습니다. 이번 포스팅에서는 어떤 암호 시스템을 다루어볼까 고민하다가 NIST에서 진행하는 PQC contest의 3라운드 7개의 후보 중에서 5개가 Lattice-based인 만큼 Lattice를 기반 문제로 사용하는 SABER 암호의 동작 원리, 장단점을 소개해보려고 합니다. 저도 불과 한달 전까지만 해도 PQC에서 사용하는 Lattice에 대해 아주 얕은 지식만을 가지고 있었기 때문에 Lattice를 잘 모르더라도 글을 이해하는데 큰 어려움은 없습니다. 다만 Group Theory가 많이 쓰이기 때문에 Group Theory에 대한 이해가 약하시면 내용을...
-
NP-Complete 게임들과 그 증명
안녕하세요? 우리가 여가 시간에 많이 즐기는 친숙한 여러 게임들, 가령 루빅스 큐브(의 최단거리 찾기), 스도쿠와 같은 고전적인 게임들부터 지뢰찾기, 테트리스, 솔리테어, 팩맨, 슈퍼 마리오, 캔디 크러쉬 사가, 2048, 루빅스 큐브, 쿠키 클리커 등과 같은 게임은 NP-Complete 문제임이 증명되어 있습니다. 이번 글에서는 이러한 게임들을 어떠한 decision problem으로 정의하면, 이러한 문제들이 NP-Complete가 되고 이를 어떻게 증명할지에 대해 알아보겠습니다. P 문제와 NP 문제 P와 NP, 그리고 NP-Hard와 NP-Complete가 어떠한 것인지는 널리 잘 알려져 있습니다. 멤버십 블로그에서도 기존에 이와...