P versus NP : exemple dans un réseau social | Rachid Guerraoui

Est ce que l'on peut être un grand mathématicien si on est juste capable de dire qu'un raisonnement est correct? Voici ce qui peut décrire l'un des problèmes les plus fondamentaux en complexité: un problème dont la solution est simple à vérifier est il simple à résoudre? En des termes plus précis: l'ensemble des problèmes dont la VERIFICATION est de complexité polynomiale et il égal à celui des problème dont la SOLUTION est de complexité polynomiale? Cette question est abordée ici à travers un exemple simple: celui de trouver une "clique" dans un réseau social.