Communication complexity of two decision problems

Communication complexity of two decision problems

0.00 Avg rating0 Votes
Article ID: iaor19931119
Country: Netherlands
Volume: 39
Issue: 2
Start Page Number: 161
End Page Number: 163
Publication Date: Oct 1992
Journal: Discrete Applied Mathematics
Authors: , ,
Keywords: decision theory
Abstract:

The authors observe that the communication complexity for deciding whether two permutations in Sn have a common inversion is log2 (n!), and that for deciding whether two integers ¸•n are relatively prime is log2(6n/;2)+O(n’-1’/2).

Reviews

Required fields are marked *. Your email address will not be published.