This paper evaluates the paradigm that proposes to quantify short-term complexity and detect nonlinear dynamics by exploiting local nonlinear prediction. Local nonlinear prediction methods are classified according to how they judge similarity among patterns of L samples (i.e., according to different definitions of the cells utilized to discretize the phase space) and examined in connection with different types of surrogate data: 1) phase-randomized or Fourier transform based, FT; 2) amplitude-adjusted FT, AAFT; 3) iteratively-refined AAFT, IAAFT, preserving distribution IAAFT-1; 4) IAAFT preserving power spectrum, IAAFT-2. The methods were applied on ad-hoc simulations and on a large database of short heart period variability series (approximately 300 cardiac beats) recorded in healthy young subjects during experimental conditions inducing a sympathetic activation (head-up tilt, infusion of nitroprusside, or handgrip), a parasympathetic activation (low dose administration of atropine or infusion of phenylephrine), a complete parasympathetic blockade (high dose administration of atropine), or during controlled respiration at different breathing rates. As to complexity analysis we found that: 1) although complexity indexes derived from different methods were different in terms of absolute values, changes due to experimental conditions were consistently detected; 2) complexity was significantly decreased by all the experimental conditions provoking a sympathetic activation and by controlled respiration at slow breathing rates. As to detection of nonlinearities we found that: 1) IAAFT-1 and IAAFT-2 surrogates performed similarly in all protocols; 2) FT and IAAFT surrogates detected about the same percentage of nonlinear dynamics in all protocols; 3) AAFT surrogates were inappropriate with all the methods and should be dismissed in future applications; 4) methods based on overlapping cells with variable size were characterized by a larger rate of false detections of nonlinear dynamics; 5) short-term heart period variability at rest was mostly linear; 6) controlled respiration at slow breathing rates increased nonlinear components, while the separate activation of the two branches of the autonomic nervous system (i.e., sympathetic or parasympathetic) was ineffective at this regard.