Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision | Next revision Both sides next revision | ||
|
sav08:remarks_on_ws1s_complexity [2009/04/17 15:23] vkuncak |
sav08:remarks_on_ws1s_complexity [2009/04/29 10:56] vkuncak |
||
|---|---|---|---|
| Line 10: | Line 10: | ||
| * [[http://theory.csail.mit.edu/~meyer/stock-circuit-jacm.pdf|Cosmological Lower Bound on the Circuit Complexity of a Small Problem in Logic]] (See the introduction and the conclusion sections) | * [[http://theory.csail.mit.edu/~meyer/stock-circuit-jacm.pdf|Cosmological Lower Bound on the Circuit Complexity of a Small Problem in Logic]] (See the introduction and the conclusion sections) | ||
| - | * circuit versus assymptotic time complexity (uniformity, specific instance versus assymptotic bound) | ||
| - | * the density question | ||
| - | * do we need to know how to check validity for all MSOL formulas | ||