はじめに 深夜3時. 大学院生は今日も不安を抱えながら勉強するふりをしている*1.最近, NP完全とNP困難, NPに関して整理をした. 勉強していて驚いたことを紹介する. 発端は, WikipediaにあったNP困難について記載されているページの以下の一文である. NP完全…

こんにちは. 卒業研究も一息つき, 春休みがやってきました. 論文を読んでいる中で, 難しい問題を取り扱っていると, その問題の難しさに関する論文や, その問題がどれくらい難しい問題なのかというのを理解するために, 計算量理論を勉強しないとなぁと感じて…