FYI: Joint Seminar on Theoretical Computer Science
Towards Capturing Order-Independent P
Neil Immerman
College of Information and Computer Sciences, University of Massachusetts Amherst, Amherst, MA, USA
College of Information and Computer Sciences, University of Massachusetts Amherst, Amherst, MA, USA
2016/5/11 Wed 4PM-5PM (E3-1, Room 3445)
In Descriptive Complexity we characterize the complexity of decision problems by how rich a logical language is needed to describe the problem. Important complexity classes have natural logical characterizations, for example NP is the set of problems expressible in second order existential logic (NP = SOE) and P is the set of problems expressible in first order logic, plus a fixed point operator (P = FO(FP)).
The latter characterization is over ordered graphs, i.e. the vertex set is a linearly ordered set. This is appropriate for computational problems because all inputs to a computer are ordered sequences of bits. Any ordering will do; we are interested in the order-independent properties of graphs. The search for order-independent P is closely tied to the complexity of graph isomorphism. I will explain these concepts and the current effort to capture order-independent P.
The latter characterization is over ordered graphs, i.e. the vertex set is a linearly ordered set. This is appropriate for computational problems because all inputs to a computer are ordered sequences of bits. Any ordering will do; we are interested in the order-independent properties of graphs. The search for order-independent P is closely tied to the complexity of graph isomorphism. I will explain these concepts and the current effort to capture order-independent P.