It is well known that some major complexity classes, like P or NP, admit a full logical characterization (e.g NP = existential 2nd order logic by Fagin's theorem). On the other hand, one can also define complexity classes in communication complexity (where P = problems solvable with poly(logN) communication etc. - see Complexity classes in communication complexity theory for more).

My question is - are any descriptive complexity characterizations known for communication complexity classes (or do any such results from standard complexity classes transfer to communication setting easily)?

  • $\begingroup$ You may want to limit the computational power of the parties, which is not done in the usual communication complexity models. $\endgroup$ Nov 20, 2011 at 12:13


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.