We investigate the computational complexity of finding local solutions for many contrastive learning settings based on triplet constraints (anchor-positive-negative paradigm), and we prove that reaching local optima cannot be done in polynomial time.