Skip to main content
Home
plus.maths.org

Secondary menu

  • My list
  • About Plus
  • Sponsors
  • Subscribe
  • Contact Us
  • Log in
  • Main navigation

  • Home
  • Articles
  • Collections
  • Podcasts
  • Maths in a minute
  • Puzzles
  • Videos
  • Topics and tags
  • For

    • cat icon
      Curiosity
    • newspaper icon
      Media
    • graduation icon
      Education
    • briefcase icon
      Policy

      Popular topics and tags

      Shapes

      • Geometry
      • Vectors and matrices
      • Topology
      • Networks and graph theory
      • Fractals

      Numbers

      • Number theory
      • Arithmetic
      • Prime numbers
      • Fermat's last theorem
      • Cryptography

      Computing and information

      • Quantum computing
      • Complexity
      • Information theory
      • Artificial intelligence and machine learning
      • Algorithm

      Data and probability

      • Statistics
      • Probability and uncertainty
      • Randomness

      Abstract structures

      • Symmetry
      • Algebra and group theory
      • Vectors and matrices

      Physics

      • Fluid dynamics
      • Quantum physics
      • General relativity, gravity and black holes
      • Entropy and thermodynamics
      • String theory and quantum gravity

      Arts, humanities and sport

      • History and philosophy of mathematics
      • Art and Music
      • Language
      • Sport

      Logic, proof and strategy

      • Logic
      • Proof
      • Game theory

      Calculus and analysis

      • Differential equations
      • Calculus

      Towards applications

      • Mathematical modelling
      • Dynamical systems and Chaos

      Applications

      • Medicine and health
      • Epidemiology
      • Biology
      • Economics and finance
      • Engineering and architecture
      • Weather forecasting
      • Climate change

      Understanding of mathematics

      • Public understanding of mathematics
      • Education

      Get your maths quickly

      • Maths in a minute

      Main menu

    • Home
    • Articles
    • Collections
    • Podcasts
    • Maths in a minute
    • Puzzles
    • Videos
    • Topics and tags
    • Audiences

      • cat icon
        Curiosity
      • newspaper icon
        Media
      • graduation icon
        Education
      • briefcase icon
        Policy

      Secondary menu

    • My list
    • About Plus
    • Sponsors
    • Subscribe
    • Contact Us
    • Log in
    • A conversation with Stephen Cook

      25 January, 2018

      Stephen Cook is a pioneering mathematician and computer scientist. Back when computers were still made of vacuum tubes Cook started thinking about the complexity of computer algorithms and came up with the concept of NP complete problems. Last year we had the pleasure of meeting Cook at the Heidelberg Laureate Forum and (along with other journalists) asked him questions about his work, computers more generally, and artificial intelligence. To find out what NP complete problems are, read What's your problem?. Otherwise, scroll to be below the video for a quick reminder.

      You can read a transcript of the interview here.

      An extremely superficial look at some complexity classes

      Problems in the P class are thought of as easy (in that a computer algorithm can solve them in a feasible amount of time) and that problems in the NP class are generally thought to be harder (in that even a computer might take billions of years to solve them). NP complete problems can be thought of as the hardest problems in NP, and they are all equivalent: if you can solve one, you can solve the others too.

      This hierarchy of complexity leads to one of the most famous questions in mathematics: are there problems in NP that are really harder than P ones, or is it that we just haven't found the best algorithms to solve them yet? It's know as the P versus NP problem.

      A famous problem in this context is the travelling salesman problem: given a number of cities, find the shortest route that visits every city exactly once. The problem is thought to be NP-hard (at least as hard as any problem in NP), but we can't rule out that one day someone will find an optimal algorithm to solve it.

      • Log in or register to post comments

      Read more about...

      computer science
      complexity
      P versus NP
      artificial intelligence
      video
      HLF
      University of Cambridge logo

      Plus Magazine is part of the family of activities in the Millennium Mathematics Project.
      Copyright © 1997 - 2025. University of Cambridge. All rights reserved.

      Terms