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 journey shown through a set of tick box cubes

    Maths in a minute: NP versus coNP

    16 November, 2026

    This article is about a complexity class called coNP, which is related to the complexity class called NP. If you don't know what NP is, then read this article first.

    A famous example of an NP problem is the decision travelling salesperson problem (DTSP). Given a list of cities and distances between them, and a distance budget d, the problem asks whether there's a route which visits every city exactly once, ends where it started, and has length at most d. Nobody knows whether there's an efficient (i.e. polynomial time) algorithm that solves all instances of this problem. However, if you're given a potential solution for an instance of the problem (i.e. a route which fits the bill for a given list of cities and distance d), you can check if it's correct in polynomial time. 

    Note that, like all NP problems, DTSP has a "yes/no" answer. While there's a polynomial time algorithm to check a potential "yes" answer,  nobody knows of a polynomial time algorithm to solve the entire problem. 

    The co-NP version of DTSP asks the negation of DTSP: whether every valid route through the cities is longer than d. A "yes" answer for the co-NP version corresponds to a "no" answer to the original version and vice versa.  So for the co-NP version there's a polynomial time algorithm to check a "no" answer, but no known polynomial time algorithm for solving the problem exists.

    This illustrates the general definition of the class of co-NP problems: they are decision problems for which a "no" answer can be checked in polynomial time.

    Could NP=coNP?

    Could it be that the NP and coNP classes are actually the same? 

    Let's look at DTSP again. Since it's in NP we can check a "yes" answer, so that's a route that potentially fits the bill, in polynomial time. If it were also in coNP, then this would mean that we can check a "no" answer in polynomial time. A "no" answer says that there isn't such a route and it would have to come with a proof of this fact. One way of proving there isn't a valid route would be to list every possible route and rule it out — but this would give a proof that's far too long to check in polynomial time. It may be that a cleverer proof which does work in polynomial time exists, but most mathematicians don't think it likely. 

    This example illustrates the general intuition. While nobody has as yet been able to prove it, the consensus is that that NP  probably isn't equal to coNP

    How does this relate to P versus NP?

    The question of whether P=NP is one of the biggest open problems in maths (find out more here). How does coNP fit into all this?

    If it turns out that P=NP, then we immediately know that NP=coNP. That's because P=NP implies that every problem in the NP class can be solved in polynomial time. An answer to the NP version of the problem (such as "yes, a valid route through the cities exists" or "no, it doesn't exist") also gives you an answer to the coNP version. Therefore the coNP version would also be in the P class, giving P=NP=CoNP.  

    Conversely, if it turns out that  NP ≠  coNP then we immediately know that P ≠  NP. 

    Could it be that P ≠  NP, but NP=coNP? This would mean that there's a problem that can't be solved in polynomial time, but for which we know for sure that both "yes" and "no" answers can be checked in polynomial time. It's a mathematical possibility, but it seems rather odd. So while nobody has been able to prove it, the general consensus is that both P ≠  NP and NP ≠  coNP.


    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

    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!

    article
    icon

    How maths can make you rich and famous

    One million dollars is waiting to be won by anyone who can solve one of the grand mathematical challenges of the 21st century. But be warned...these problems are hard. In the first of two articles, Chris Budd explains how to hit the bigtime.

    Read more about...

    P versus NP
    complexity
    Travelling salesman problem
    Maths in a minute

    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