  Although noise-based logic shows potential advantages of reduced power
dissipation and the ability of large parallel operations with low hardware and
time complexity the question still persist: is randomness really needed out of
orthogonality? In this Letter, after some general thermodynamical
considerations, we show relevant examples where we compare the computational
complexity of logic systems based on orthogonal noise and sinusoidal signals,
respectively. The conclusion is that in certain special-purpose applications
noise-based logic is exponentially better than its sinusoidal version: its
computational complexity can be exponentially smaller to perform the same task.
