A very hard problem that only has very inaccurate bounds is how many numbers can one choose between 1 and n if no three of them are allowed to lie in an arithmetic progression?

How many steps are needed to multiply together two n digit numbers?

A similar problem is how to compute the multiplication of two n x n matricies efficiently?

It has been shown that even normalized gaps between two succesive prime numbers can be arbitrarily large, proved by Westzynthius in 1931. There are also infinitely primes for which p and p + 2 is also a prime, proved by Goldston, Pintz and Yildirim in 2005.

Given a mathematical structure and a selection of properties that it has then which combinations of properties imply which other ones?