The prediction of the most stable, prevalent and/or functional structure adopted by an RiboNucleic Acid molecule (RNA) is an old, yet very much ongoing, challenge of computational biology. Currently available computational methods, such as MFold or RNAfold, somehow artificially restrict their search space to tree-like conformations, the secondary structures. However, such a definition intrinsically discards complex topological motifs that are both observed in experimentally-determined structures, essential for the functions performed by the molecule, and conserved throughout the evolution. In this talk, I will review two decades of works aiming at characterizing the complexity of minimizing the free energy of a given RNA molecule, while allowing (limited subsets of) pseudoknots/crossing interactions. The general hardness of the associated computational problems motivates the development of novel parameterized-complexity approaches and heuristics, as further illustrated by the follow up talk by H Orland. This is a joint work in collaboration with S. Sheikh (Bloomberg R&D, USA) and R Backofen (Uni. Freiburg, Germany).