We’re entering an era where CPU clock speeds will soon cease to scale upwards and instead CPU manufacturers are planning to put more and more independent cores on a chip. Intel plans to release an 80-core chip within 5 years. Consequently the research community is setting their eye on the manifold barriers to writing correct…

# Tag: Theory

## Robin’s theorem

Most computer scientists are familiar with the P = NP problem, which asks essentially whether we can verify more problems in polynomial time than we can solve. So fundamentally does complexity theory hinge on this result that the Clay Mathematics Institute has labelled it one of their seven Millennium Prize Problems, and will award $1,000,000…

## Modular arithmetic and primality testing

Number theory is, roughly speaking, the study of properties of integers. Often a problem which is easy for real numbers, such as factoring or linear programming, seems to be considerably more difficult when restricted to integers (in fact, integer programming is NP-hard). Much of the focus of modern number theory is on solving these problems…