It seems that Ben Rossman has resolved another long-standing open problem in finite model theory: finite-variable hierarchy conjecture. Loosely speaking, the conjecture is that over ordered graphs first-order logic with k+1 variable is more powerful than first-order logic with k variable. The problem is nicely summarized in Anuj Dawar's survey. Ben has shown that this hierarchy is strict. What was previously known is that (over ordered graphs) first-order logic with 3 variables is strictly more expressive than first-order logic with 2 variables, but it was not known whether first-order logic with 3 variables is less expressive than first-order logic with k variables, for every k > 3. Worse yet, it wasn't even known whether this hierarchy is strict. See Anuj Dawar's survey for further details.
I believe this is the third big open problems that Ben has resolved in this decade. Go Ben!
29 comments:
notes that are beneficial to my knowledge,
articles that I like
thank you for your sharing.it is very good.
so many that I can take from this blog very helpful.
i like your article, thanks to sharing master :)
time is very valuable and can not be repeated, thanks to the article master
i like your blog, thanks to information :)
i like your blog, thanks to information :)
Very beautiful, this blog write very meaningful,your article is really Great :)
your articles that I like :)
thank you. awaited next article :)
thank you for sharing this information very useful :)
I strongly agree with your article :)
i like your article, thanks to sharing master :)
thank you for sharing this information very useful :)
thanks for knowledge master :)
thanks for knowledge master :)
I strongly agree with your article :)
Good! Wish everybody wrote so :)
thank you. awaited next article :)
thanks to sharing master
demonstration of interest :)
thanks for knowledge master :)
notes that are beneficial to my knowledge, thanks :)
so many that I can take from this blog very helpful. :)
thank you for the information :)
I really enjoyed every article written on this blog :)
very useful information :)
thanks to article master :)
Post a Comment