Programmer's Guide To Theory - NP & Co-NP
Written by Mike James   
Monday, 25 November 2019
Article Index
Programmer's Guide To Theory - NP & Co-NP
Function Problems

Function Problems

One of the disadvantages of high profile classes like NP is that many function problems that sound as if they might reduce to a decision problem in NP don’t. For example, the problem of finding the shortest path through a network clearly isn't a suitable candidate for NP. Why not? Because you cannot supply a witness that verifies that a path is the shortest in polynomial time. If I provide you with a path that I claim is shortest you still have to compare it to all the other possible paths to prove that it is, which is clearly not in polynomial time.

Compare this to the seemingly similar problem of proving that a given path is not the shortest - i.e. you don't actually have to find the shortest path, just prove that the one given is or is not the shortest. This is NP because all that has to be done is to provide an example path, i.e. one path, that is shorter. There is no requirement to compare it to every possible path, just to one that is actually shorter. Thus, given a path A it clearly isn't the shortest if you are given the extra piece of information that path B is shorter, i.e. B is a witness that A isn't the shortest path.

Perhaps the best known “difficult” problem is the TSP – Traveling Salesman Problem. Given a list of cities simply find the shortest route that visits each city and returns to the starting point. Clearly this is not in NP because no witness verifiable in polynomial time can be found. If I give you a candidate path you cannot verify it is the shortest without searching the entire solution space for the shortest. The witness doesn't help.

As before, we can turn it into an NP problem by changing the question to “is there a route shorter than L”. This is in NP, but it isn’t the full TSP problem. We will return to these not-quite NP problems later, in the context of NP-hard problems.

The Hamiltonian Problem

Another well known example is the Hamiltonian. A graph (another name for a network) is said to be “Hamiltonian” if there is a path through it visiting each node exactly once.

The graph in the diagram below is Hamiltonian because there exists a path that visits each node exactly once - shown on the right.

hamiltonian

 

The following should be fairly obvious to you now:

  1. Is proving that a graph is Hamiltonian in P?
    No, it takes exponential time to find a path that visits each node by examining each path until you find one that is Hamiltonian.

  2. Is proving that a graph is not Hamiltonian in P?
    Obviously not, because you have to check every path to prove that a suitable one doesn't exist and so this must take longer on average than (1).

  3. Is proving that a graph is Hamiltonian in NP?
    Yes. The witness is a path that visits each node exactly once. Once you have the description of such a path, checking that it visits each node only once is trivial and obviously in P.

  4. Is proving that a graph is not Hamiltonian in NP?
    Probably not because you can't give a piece of information that allows someone to check that a suitable path doesn't exist. You have no choice but to check them all and that's clearly the same as (2).

  5. Is proving that a graph is not Hamiltonian in co-NP?
    As it is the complement of the original problem, which is in NP, it is in co-NP.

Not included in this extract:

  • Boolean Satisfiability
  • NP-Complete and Reduction
  • Proof That SAT Is NP-Complete
  • NP-Hard
  • What if P = NP?

Summary

  • We generally recognize two types of algorithm - function evaluation and decision problems. However, function evaluation can be converted into a decision problem.
  • NP decision problem are easy to check if you have a proposed solution, a witness, but otherwise may be hard to solve. Any problem for which a witness exists can be checked in polynomial time and is therefore in NP.

  • A problem in NP needs, at most, exponential time and thus
    P ⊆ NP ⊆ Exp.

  • Co-NP problems are derived from NP problems by changing the decision around. For example, "is there a subset that sums to zero" is in NP, whereas "there is no subset that sums to zero" is in co-NP. It isn't known if all co-NP problems are also in NP.

  • The Boolean satisfiability problem, CircuitSAT, is an archetypal NP problem - find the inputs to a Boolean circuit that produces a true output.

  • There are many variants on the more general SAT problem. The k-SAT problem restricts the form of the Boolean function to use nothing but k inputs ANDed together and then ORed with other similar clauses. What is surprising is that 2-SAT is in P, but k-SAT for k>2 is in NP.

  • One of the most important theorems in computer science is that k‑SAT for k>2 or CircuitSAT is NP-complete. That is, any problem in NP can be reduced to SAT. What this means is that if a polynomial algorithm exists for any NP-complete problem then there is a polynomial algorithm for all NP problems and P=NP.

  • NP-hard problems are NP-complete problems that are not necessarily in NP. If you were to find a polynomial solution to any NP-hard problem then P=NP. Problems in NP cannot be harder than NP-hard problems.

  • The consequences of proving P=NP are often assumed to be serious – cryptographic codes would suddenly be insecure, for example. However, the concept of a "galactic" algorithm puts this idea in perspective. A galactic algorithm is one that only achieves its asymptotic performance for galactically large values of problem. If P=NP but only for a galactic polynomial algorithm, then nothing has changed from a practical point of view.

A Programmers Guide To Theory

Now available as a paperback and ebook from Amazon.

cover600

Contents

  1. What Is Computer Science?
    Part I What Is Computable?
  2. What Is Computation?
  3. The Halting Problem
  4. Finite State Machines
    Extract 1: Finite State Machines
  5. Practical Grammar
  6. Numbers, Infinity and Computation
    Extract 1: Numbers 
    Extract 2: Aleph Zero The First Transfinite
    Extract 3: In Search Of Aleph-One
    Extract 4: Transcendental Numbers
  7. Kolmogorov Complexity and Randomness
    Extract 1:Kolmogorov Complexity 
  8. The Algorithm of Choice 
  9. Gödel’s Incompleteness Theorem
  10. Lambda Calculus ***NEW!
    Part II Bits, Codes and Logic
  11. Information Theory 
  12. Coding Theory – Splitting the Bit
  13. Error Correction 
  14. Boolean Logic
    Part III Computational Complexity
  15. How Hard Can It Be?
    Extract 1: Where Do The Big Os Come From
  16. Recursion
    Extract 1: What Is Recursion
    Extract 2: Why Recursion
  17. NP Versus P Algorithms
    Extract 1: NP & Co-NP
    Extract 2: NP Complete

<ASIN:1871962439>

<ASIN:1871962587>

 

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.

Banner


FORTRAN and COBOL Re-enter TIOBE Index
17/05/2024

The TIOBE Index sets out to reflect the relative popularity of  computer languages so it comes as something of a surprise to see two languages dating from the 1950's in this month's Top 20.



Google Reduces Support For Python, Dart And Flutter
01/05/2024

There are many reports that Google has removed people from its Python, Dart and Flutter teams and possibly more. What does this say about relying on Google as a source of technology for your projects? [ ... ]


More News

raspberry pi books

 

Comments




or email your comment to: comments@i-programmer.info



Last Updated ( Monday, 25 November 2019 )