-
Introduction to APSP Conjecture and BMM Conjecture
Introduction to APSP Conjecture and BMM Conjecture 이론전산학에서 논의되는 가장 주된 문제 중 하나는 어떠한 문제가 “쉽다” (algorithm) 내지는 “어렵다” (hardness) 는 논의이다. 쉽다는 것을 증명하려면, 효율적인 알고리즘을 찾아 빠르게 해결하면 된다 (constructive proof). 대단히 명료하고, 알고리즘 대회를 통해서 많이 연습되는 방법이기도 하다. 어렵다는 것을 증명하는 것은 쉽다를 증명하는 것만큼 명료하지 않다. $P=NP$ 가설이 오랜 난제로 남아있는 것도 “어려움을 증명하는” 쉬운 방법을 찾지 못해서라고 볼 수 있다. 통상적으로는, 가장 대표성있는 문제를 잡아서 “어떠한 문제는 풀...
-
Exploring Simulated Annealing for Derivative-free Optimization 1
Exploring Simulated Annealing for Derivative-free Optimization 1 현대 과학 및 수학에서, 많은 종류의 하이퍼파라미터를 갖는 문제의 최적의 솔루션을 찾는 것은 매우 중요한 문제입니다. 특히, 머신러닝, 딥러닝의 등장으로, 굉장히 어려운 형태의 최적화 문제의 좋은 솔루션을 구하는 것은 모델의 품질 향상과 밀접한 연관을 갖게 됩니다. 이 과정에서 다양한 종류의 optimizatino problem을 해결하게 되고, 그 과정에서 gradient 기반 접근 방법이 굉장히 많이 사용되고 있습니다. 그러나 최적화 문제 중에서는 특정 상태에 대한 gradient를 구하는 것이 어려운 문제들이 있습니다. 이러한...
-
Spring Boot: Containerize
들어가며 Spring Boot 애플리케이션의 컨테이너 이미지화 방법을 살펴보고 그 방법들의 장단점을 알아보려 한다. 컨테이너 이미지화 Dockerfile FROM azul/zulu-openjdk-centos:11 RUN mkdir -p /opt/spring-boot-app/logs RUN touch /opt/spring-boot-app/logs/gc.log ADD ./build/libs/spring-boot-app.jar /opt/spring-boot-app.jar EXPOSE 8080 ENTRYPOINT ["java", "-jar", "/opt/spring-boot-app.jar"] 상당히 간단한 형태이다. 다만 보다시피 JAR 파일을 통째로 넣으므로 모든 빌드의 통째 결과가 새로운 레이어로 생성된다. 이는 즉 저장소의 용량을 더 많이 차지한다는 것이고, 새로운 버전의 시작 대기 시간도 더 많은 용량을 다운로드해야 하므로 더 길어짐을 의미한다. 그나마 다른 도구를 추가하기는...
-
Using linear-optical quantum computing model to prove #P-hardness of Permanent
Introduction 지난 달 작성한 글과, 최근 진행하는 project-hardness 스터디를 진행하면서 $\sharp P$-hardness에 대한 내용을 자주 다루었습니다. 하지만 $\sharp P$라는 complexity가 고안된 근본적인 이유와도 같은 permanent에 대해서는 언급하지 않았습니다. Shortest Even Cycle Problem을 다룬 문제에서 지나가듯 이야기했지만 길게 이야기하지 않았죠. 실제로 이 문제를 해결한 Valiant(1979)의 논문은 3000회가 넘는 인용수를 기록했으며, Permanent를 비롯한 수많은 복잡도 이론에 대한 공헌으로 Valiant은 튜링상까지 수상하게 됩니다. 이런 위대한 업적에도 불구하고 Valiant이 어떤 아이디어로 Permanent의 hardness를 증명했는지는 비교적 알려져 있지 않은데, 문제...
-
SMAWK algorithm
들어가며 SMAWK 알고리즘은 $n \times m$ 크기의 totally monotone한 행렬에서 모든 행마다 최솟값의 위치를 $O(n+m)$ 시간에 구하는 알고리즘이다. 이 글에서는 SMAWK 알고리즘에 대해 소개하고, 이를 통해 해결할 수 있는 문제들에 대해 소개한다. 단조성. $2 \times 2$ 행렬 $\left[ {\begin{array}{ccc}a & b \ c & d \ \end{array}} \right]$ 은 다음 조건이 성립하면 monotone하다고 한다. $c < d$이면 $a<b$이다. $c=d$이면 $a\leq b$이다. $n \times m$ 행렬은 만약 모든 $2 \times 2$ 부분행렬이 monotone하다면 totally monotone하다고 한다....