18

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)?

Marcin Kotowski
  • 2,806
  • 19
  • 25
  • You may want to limit the computational power of the parties, which is not done in the usual communication complexity models. – MassimoLauria Nov 20 '11 at 12:13

0 Answers0