papa本第10回参加メモ

p38「proof」から p39「Proof of the Lemma」まで読んだ。次回はp40 4行目「Suppose that ...」から

これまでの勉強会で一番面白かったです。 毎度適当なメモなんで読むのに適さないですです。

Theory of Database Concurrency Control

connpass.com

Theorem 2.4

• p39 二行目typo(B,C,A)⇨正しくは(A,C,B)

• P(s)がtotal orderであることを証明できればVSR

  • ただしその検査はNP-complete 　

    Theorem2.5

Lemma 2.3

補題。

• SAT問題でclauseの分類

  • 否定のみのリテラルから作られるclause⇨negative clause
  • 否定のリテラルがないclause⇨positive clause
  • 否定と肯定のリテラルが混ざったclause⇨ mixed
  • mixedなclauseで構成されていない式⇨simple formula

• Lemma 2,3:リテラルのsimple formulaのみから構成されている式の検査⇨NP完全

SATISFIABILITY remainss NP-complete even if it is restricted to simple formulae with two or three literals per clause.

• これは言い過ぎなのでは？という議論が発生
• two or three literalsという単語の意味は？twoっている？

• 2SAT 3SATなどの議論

  • 2SATがPなのはなぜか？(3項の句が一つでもあると総当たりになる)

• originalとかinitialとかややこしい単語が多すぎる。

• NP-completeの証明(3SATからの帰着)にんみんなで感動した。