Abstract
Computational complexity of graphs is the smallest number of union and intersection operations required to generate them when starting from simplest sets of edges: stars or cliques. An intriguing aspect of this measure is its connection to circuit complexity of Boolean functions and, in particular, with the P versus NP question. We survey this connection as well as known bounds on the complexity of explicit graphs.