However, little more was known until the early 1990s, when several authors began to make connections between the approximation of maximum cliques and probabilistically checkable proofs.
Cu toate acestea, nu se cunoșteau prea multe până la începutul anilor 1990, atunci când mai mulți autori au început să facă conexiuni între aproximarea clicilor maxime și demonstrațiile probabilistic verificabile⁠(d).