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 group of cubes, mostly showing red X with one yellow tick

    Maths in a minute: The SAT problem

    16 November, 2026

    This article looks at a famous, but quite abstract, example of a NP problem. For a slightly more accessible description of an NP problem, see here.

    Sometimes the truth is binary. There are statements which are either true or false with nothing in between. Examples are "4 is an even number" or "London and Birmingham are less than 200 km apart". There are also statements that aren't quite so binary. Examples include "sloth is sinful" and "cutting taxes is good". Not only are these a matter of opinion, they could also be true in some ways and false in others.

    It won't come as much of a surprise that mathematics is very comfortable with statements of the former kind. There's a whole system of logic, called propositional logic, built around them. The system doesn't care about the actual content of such statements. Instead, it tells you what their being true or false means for combinations of them.

    As an example, imagine that P and Q are two binary statements — these are also known as Boolean statements after the mathematician George Boole. Then propositional logic decrees that the statement  P AND Q is true if both P and Q are true, otherwise it is false. Checking against real life, this makes sense. The statement "4 is an even number and London and Birmingham are less than 200 km apart" is true if and only if both parts are true.  

    Propositional logic also decrees that the statement NOT(P) is true when P is false and vice versa. This also makes sense. And it means that the statement  P AND NOT(P)  can never be true, since one of its components will always be false. See this article to find out more about propositional logic.

    Here is an example of a composite statement from propositional logic involving three constituent statements A, B, and C:

     

    A AND NOT(B AND C)

     

    For the assignment A=true, B=true, C=false the statement evaluates to true. Hence the statement is satisfiable. 

    Using the rules of propositional logic you can string individual statements together to your heart's content, giving you composite statements that are as long as you like. (See the box for an example of a statement made up of three components.)

    Given such a composite statement, you might ask yourself if it can ever be true: is there an assignment of truth values to its constituent components that makes the overall statement true?  If yes, then the statement is considered satisfiable. The problem of finding out whether a given statement is satisfiable is known as the satisfiability problem also often denoted by SAT.

    SAT is NP

    How do you solve SAT for a given statement from propositional logic? One way is to try out all possible assignments of truth values to its constituent parts. In our example in the box, this would mean trying all ways in which you can assign the values "true" and "false" to each of A, B, and C in the statement, so you would be going through combinations of the form

    A=true, B=true, C=true

    A=true, B=true, C=false

    A=true, B=false, C=true,

    and so on. If there are many constituent parts, then this could take an awfully long time — and the longer the statement, the longer it will take.

    Indeed, nobody knows of a general algorithm for solving SAT for any given statement whose execution time doesn't explode as the length of statements increases. To be precise, nobody knows of a polynomial time algorithm for the SAT problem (find out more here). Note that "execution time" here doesn't mean the time it takes to solve the problem as measured on a clock — that would depend on the speed of your computer. Instead it refers to the number of steps the algorithm has to execute. Polynomial time algorithms are considered efficient, not because this number of steps is always low, but because it grows in a relatively tame way as the length of the problem increases. 

    While a polynomial time solution for SAT remains elusive, the problem comes with another interesting feature. If I gave you a possible solution for a given statement from propositional logic — an assignment of truth values to individual components which I claim makes the overall statement true — then checking that this solution is correct is comparatively quick. There is a polynomial time algorithm for doing this.

    Problems of this nature, for which a potential solution can be checked in polynomial time, are known as NP problems. There's quite a few of them around. Another example is the decision travelling salesperson problem. Given a list of cities and a distance d,  the task is to see if there's a route that visits every city exactly once, returns to where it started, and has length at most d. A brute force solution would involve looking at all possible routes and seeing if one fits the bill.  The time it takes to do this will grow very fast as the number of cities grows, but checking whether a given route is a solution is relatively quick.  Another example of an NP problem is the decision knapsack problem (find out more here).

    SAT is NP complete

    How does SAT fit into the jumble of NP problems? Back in the early 1970s Stephen Cook and Leonid Levin independently proved that it can embody them all. 

    Given any instance of an NP problem (e.g. the decision travelling salesperson problem for a given list of cities), you can create a (possibly giant) statement from propositional logic. If this statement is satisfiable, then the answer to the original NP problem is "yes" (e.g. there is a route of the required length). If the logic statement isn't satisfiable, then the answer to the original NP problem is "no" (there isn't such a route). The translation of the original NP problem to the logic statement can be done efficiently, that is, in polynomial time. 

    NP problems which have this property — that all instances of all other NP problems can be translated into them in polynomial time — are known as NP complete. SAT was the first NP complete problem to ever be discovered. 

    Why do we care about all this so much? We said above that nobody knows of polynomial time algorithms for solving NP problems. But this doesn't mean that such algorithms don't exist.  If someone were to discover one for an NP complete problem such as SAT, then it would be possible to translate it into a polynomial time algorithm for all other NP problems. Conversely, if someone were to prove that a polynomial time algorithm doesn't exist for an NP complete problem, then this result would apply to all other NP problems too.

    This brings us to one of the biggest open problems in all of mathematics: whether the class of NP problems is actually equal to the class of problems that can be solved in polynomial time. The latter class is known as P. The overall problem is called the P versus NP problem. It's one of the seven Clay Millennium Problems: anyone who can solve it will win a million dollars. Find out more here.


    This content forms part of our collaboration with the Isaac Newton Institute for Mathematical Sciences (INI) – you can find all the content from the collaboration here.

    The INI is an international research centre and our neighbour here on the University of Cambridge's maths campus. It attracts leading mathematical scientists from all over the world, and is open to all. Visit www.newton.ac.uk to find out more.

    Isaac Newton Institute Logo
    • Log in or register to post comments

    You might also like

    article

    A conversation with Stephen Cook

    We talk to pioneering mathematician Stephen Cook, who came up with the concept of NP-complete problems, about his work, computer science, and artificial intelligence.
    article

    What's your problem?

    There are problems that are easy to solve in theory, but impossible to solve in practice. Intrigued? Then join us on a journey through the world of complexity, all the way to the famous P versus NP conjecture.

    news
    One red figure surrounded by arrows pointing to other figures

    The travelling salesperson

    It's one of the most notorious problems around and takes you straight to the frontiers of maths research. Find out more in this introduction!

    Read more about...

    P versus NP
    complexity
    Travelling salesman problem

    Our Podcast: Maths on the Move

    Our Maths on the Move podcast brings you the latest news from the world of maths, plus interviews and discussions with leading mathematicians and scientists about the maths that is changing our lives.

    Apple Podcasts
    Spotify
    Podbean

    Plus delivered to you

    Keep up to date with Plus by subscribing to our newsletter or following Plus on X, Bluesky, Facebook or LinkedIn.

    University of Cambridge logo
    Twitter / X logo Bluesky logo LinkedIn logo

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

    Terms