|
[Jun. 26th, 2008|10:06 am]
Jason
|
The first (invited) talk this morning was about a bunch of rather high-powered stuff relating logics to complexity classes, hunting around for a logic for which the predicates definable in it are exactly PTIME. Didn't realize this was an open problem, me being distracted by something the speaker mentioned early on, namely the sort of PTIME-capturing linear logics that "capture" it in a different way.
Second talk I didn't understand much about, but it got me reading about Gröbner bases, which are pretty neat, and not as scary as I assumed.
In a paragraph: if we have polynomials over one variable, we can do the standard division algorithm and find out the quotient and remainder. If we have polynomials in multiple variables, and we want to find out how to express g canonically as a polynomial combination of f_1, ... f_n and some remainder not in the ideal (f_1, ... f_n), there is a pretty obvious nondeterministic divison algorithm that tries to "reduce" against to f_1, ... f_n, but sadly the answer we get actually does depend on our nondeterministic choices. But for some special collections of f_1, ... f_n the algorithm gives a unique answer for and g we try to divide — these are called the Gröbner bases. The amazing thing is every ideal I has a Gröbner basis that generates I! Apparently this unique-division property leads to all sorts of other useful properties, too. |
|
