17
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.