Speaker
Description
A clique is a fully connected subset of an undirected graph. Finding the largest clique is NP complete problem (it takes exponential time to solve the problem).
However, if we know that the largest clique is not too large, then it is a polynomial problem. If the graph is also very sparse, then it does not have to be a polynomial of high degree, and it can be solved up to some predetermined limits.
Let's look at an ancient problem: If in the set of numbers $\{1,3,8\}$ we multiply each of its two different elements and add the number $1$ to the product, the result will be the square of a number: $$1\cdot3+1=2^2,\qquad1\cdot8+1=3^2,\qquad3\cdot8+1=5^2.$$
The curiosity of mathematicians has been tickled by similar sets for millennia, so solving such problems, the coming centuries gave birth to many new mathematical disciplines. With the advent of computers and supercomputers, many new interesting sets have been found (and are still being found).
