CSFG
English Deutsch Beta Español Beta język polski (2.6.0)
Chapters Curriculum Guides Appendices

12. Complexity and Tractability

Introduction

Are there problems that are too hard even for computers? It turns out that there are. In the chapter on artificial intelligence we saw that just having a conversation – chatting – is something computers can't do well, not because they can't speak but rather because they can't understand or think of sensible things to say. However, that’s not the kind of hard problem we’re talking about here – it's not that computers couldn’t have conversations, more that we don't know just how we do it ourselves and so we can't tell the computer what to do.

In this chapter we're going to look at problems where it's easy to tell the computer what to do – by writing a program – but the computer can’t do what we want because it takes far too long: millions of centuries, perhaps. Not much good buying a faster computer either: if it were a hundred times faster it would still take millions of years; even one a million times faster would take hundreds of years. That's what you call a hard problem – one where it takes far longer than the lifetime of the fastest computer imaginable to come up with a solution!

Next:
What's the big picture?

Chapter sections

  • 12.1. What's the big picture?
  • 12.2. Algorithms, problems, and speed limits
  • 12.3. Tractability
  • 12.4. The Travelling Salesman Problem
  • 12.5. Bin packing problem
  • 12.6. Other intractable problems
  • 12.7. The whole story!
  • 12.8. Further reading

Looking for something for primary schools? Check out CS Unplugged.

The Computer Science Field Guide is an online interactive resource for high school students learning about computer science.

Useful Links

  • About
  • Chapters
  • Interactives
  • Curriculum Guides

Community

  • Twitter
  • YouTube
  • GitHub

Help

  • Search
  • Glossary
  • Feedback

Switch to teacher mode

English | Deutsch | Español | język polski (2.6.0)

The Computer Science Field Guide material is open source on GitHub, and this website's content is shared under a Creative Commons Attribution-ShareAlike 4.0 International license. The Computer Science Field Guide is a project by the Computer Science Education Research Group at the University of Canterbury, New Zealand. Icons provided generously by icons8.

3.12.6

This definition is not available in English, sorry!