  We introduce and solve a model of interacting electrons and phonons that is a
natural generalization of the Sachdev-Ye-Kitaev-model and that becomes
superconducting at low temperatures. In the normal state two Non-Fermi liquid
fixed points with distinct universal exponents emerge. At weak coupling
superconductivity prevents the onset of low-temperature quantum criticality,
reminiscent of the behavior in several heavy-electron and iron-based materials.
At strong coupling, pairing of highly incoherent fermions sets in deep in the
Non-Fermi liquid regime, a behavior qualitatively similar to that in underdoped
cuprate superconductors. The pairing of incoherent time-reversal partners is
protected by a mechanism similar to Anderson's theorem for disordered
superconductors. The superconducting ground state is characterized by coherent
quasiparticle excitations and higher-order bound states thereof, revealing that
it is no longer an ideal gas of Cooper pairs, but a strongly coupled pair
fluid. The normal-state incoherency primarily acts to suppress the weight of
the superconducting coherence peak and reduce the condensation energy. Based on
this we expect strong superconducting fluctuations, in particular at strong
coupling.
