Tseitin transformationとは

理論計算機科学 (Thoerotical Computer Science) の色んな定理やアルゴリズムを紹介していきます. 基本的には日本語の資料がほとんどないような知見を解説していきます. 執筆者: 清水 伸高 https://sites.google.com/view/nobutaka-shimizu/home 計算複雑性理論については疎く、最近ようやく本腰を入れて勉強し始めたのですがTseitin transformationというものがとても面白かったので紹介します。こういう考え方は苦手すぎて理解にすごく時間がかかってしまう... 僕が勉強したときはwikipedia(en)とこの記事を参考にさせていただきました。 ここでは 変数 : xのこと.今回はa,b,cとかx,y,zとかで表す。 リテラル : x、!xのこと Boolean function :ここでは and, or