MGPhDThesis.hpp File Reference

Plans regarding the MG's PhD Thesis. More...

Go to the source code of this file.

Detailed Description

Plans regarding the MG's PhD Thesis.

  • An overview is needed of the structure of the thesis, key lemmas that need proving and the timeframe in which these things will be done.
Differences between MG_PhDThesis.tex and 2011_SAT_MGOK.tex
  • Below "thesis" refers to MG_PhDThesis and "report" refers to the 2011_SAT_MGOK.tex report.
  • Structural differences:
  • Differences within chapters/sections:
    • In the Width-based hardness section (sec:Widthbasedhardness):
      • In the thesis (but not the report) there is:
        • A remark on the definition of w-hardness also relate OK's width notion with old notions of width.
        • The definition of the "WC_k" class of clause-sets is defined (clause-sets of w-hardness at most k)
        • A lemma on stability properties of the WC_k classes under various actions.
        • A lemma showing that to compute w-hardness it suffices to consider partial assignments corresponding to prime implicates.
        • A section on methods for computing lower bounds on the size of k w-soft representations (without new variables) via r_k-trigger hypergraphs (including definitions + lemmas).
      • In the thesis, there is a chapter on "Extremal Strahler Trees" offering an example of a sequence of boolean functions which answers question que:hdhw.

Definition in file MGPhDThesis.hpp.