It may be a surprise to some that there are theoretical limits on a computer’s ability. Don’t worry, your next phone will run Angry Birds and Ingress faster than today. But a program that is given another program as input, will never decide whether that program will terminate or run forever. This is known as the halting problem and while it may not practically sound that limiting, it shows that there indeed are limits to what can be done with a computer.
Then there are classes of problems for which there are no known efficient solutions. Even worse, it is not known whether there can be an efficient solutions for these problems. Among computer scientists, this is known as the problem and it is this problem that Lance Fortnow has devoted his new book, The Golden Ticket, to explaining. Continue reading “This book contains The Golden Ticket of computer science”