  We consider relations between communication complexity problems and detecting
correlations (violating local realism) with no local hidden variable model. We
show first universal equivalence between characteristics of protocols used in
that type of problems and non-signaling correlations. We construct non linear
bipartite Bell type inequalities and strong nonlocality test with binary
observables by providing general method of Bell inequalities construction and
showing that existence of gap between quantum and classical complexity leads to
violation of these inequalities. We obtain, first to our knowledge, explicit
Bell inequality with binary observables and exponential violation.
