Speaker：Prabhu Manyem
Title
：Expressibility at the machine level versus structure level: ESO universal Horn Logic and the class P
时间：2013年12月20日 下午2：30
地点：集贤楼402室
Abstract：
We show that ESO universal Horn logic (existential second logic where the first order part is a universal Horn formula) is insufficient to capture P, the class of problems decidable in polynomial time. This is true in the presence of a successor relation in the input vocabulary. We provide two proofs -- one based on reduced products of two structures, and another based on approximability theory (the second proof is under the assumption that P is not the same as NP). The difference between the results here and those in (Graedel 1991) is due to the fact that the expressions this talk deals with are at the "structure level", whereas the expressions in (Graedel 1991) are at the "machine level" since they encode machine computations -- a case of "Easier DONE than SAID".
Bio：
Prabhu Manyem obtained his PhD in Discrete Optimisation from North Carolina State University, Raleigh, NC, USA in 1996. After working in the American industry for three years, he joined the University of South Australia at Adelaide in 1999 as a postdoctoral researcher. In early 2005, he moved to the University of Ballarat. Then in late 2009, he moved to Shanghai University (China). His interests are in Computational complexity, Finite model theory and Discrete optimisation.
