We study the complexity of deciding bisimilarity between non-deterministic processes with explicit primitives for manipulating data values. In particular, we consider a language with valuepassing (input/output of data) and parametric deÿnitions of processes. We distinguish the case in which data cannot be tested and the case in which a simple equality test over data is permitted. In the ÿrst case, our main result shows that the problem is PSPACE-hard for the full calculus. In the second case, we ÿrst show that the problem is coNP-complete in the fragment with value-passing and no parametric deÿnitions. We then deÿne a compositional polynomial-time translation of the full calculus to the fragment with parametric deÿnitions but no value-passing. The translation preserves bisimilarity: this fact establishes the decidability of the full calculus and shows that the fragment without value-passing is computationally equivalent to the full calculus. For the latter, bisimilarity is then proved to be EXP-complete. Finally, we add to our language a parallel composition operator and show that, for a certain restricted syntactic format, the bisimilarity problem is still decidable and EXP-complete.