Interestingly, even finding maximal cliques in small dense graphs is believed to be too hard. For example, take a graph chosen uniformly at random from all graphs on 1k vertices. We know that the largest clique has size roughly 2 log n = 20 nodes with overwhelming probability, but nobody knows how to efficiently find it with any nontrivial probability. The best we know how to do is get a log(n) size clique using the greedy algorithm.