As well as how long it takes to do a computation, you can also ask questions about how hard verification of a supposed answer is and this leads us on to the class of problems called NP – perhaps currently the most interesting of all. 

A Programmers Guide To Theory

Now available as a paperback and ebook from Amazon.

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 ***NEW!
10. Lambda Calculus
    Part II Bits, Codes and Logic
11. Information Theory 
12. 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>

Functions and Decision Problems

There are two general types of algorithm - function evaluation and decision problems. A function evaluation problem is just that – given a function f and a value x find the result y. This may sound limited but if you allow the function to be general enough it encompasses just about everything. For example, a program that gives you the nth digit of π is just evaluating the function Pi(n), i.e. the function that gives you the nth digit of π.

Alternatively you can perform a computation to answer a question – a decision problem. For example, is 9 the sixth digit of π? You can answer this question by computing Pi(6) and comparing the result to 9. As 9 is the sixth digit of π, the answer is “true”.

As well as being able to convert a decision problem into a function evaluation, you can generally convert a function evaluation into a decision problem by asking if each possible result is a solution. For example, is Pi(6) zero, is Pi(6) one and so on.

This all seems simple enough and not particularly interesting. It seems that we are just describing what we already have in terms of algorithms in slightly different ways. If it is hard to find the hundredth digit of π, then it is going to be hard to answer the question “is the hundredth digit of π a 6”. However, there are problems for which this is not the case and these are interesting.

Non-Deterministic Polynomial Problems

There are problems that are difficult to solve, but easy to check if you are provided with a confirming example. For example, if I give you a set of numbers and the decision problem, “Is there is a subset that sums to zero?” then to find out you have to examine each possible subset until you find one that sums to zero and this procedure is not in P. In fact, it is takes exponential time as the number of sets you have to examine is O(2ⁿ).

Now suppose I give you a subset that I claim sums to zero, how long would it take for you to verify that claim? All you have to do is sum the single set of numbers and thus verification is in P. The subset that settles the matter is usually called a witness. In this case the witness is for a “yes” answer to the problem. You can also think of the witness and its verification as a proof that the answer is “yes”.

So we have a decision problem that is not in P, but if you are given a witness verification is in P. This is an example of a problem in NP, Non-deterministic Polynomial time. The reason they are called Non-deterministic Polynomial is that another definition of an NP problem it that it can be solved in polynomial time by a non-deterministic Turing machine - one that has multiple alternatives at each step. You can think of it as either taking all of the alternatives or being lucky enough to take the correct branch at each step. For example, a non-deterministic Turing machine for the sub-set sum problem would examine each sub-set in parallel and return the one first one that summed to zero. As this is equivalent to checking a witness, it is clear that it can be done in polynomial time.

A deterministic Turing machine verifying a witness in polynomial time is the same as a non-deterministic Turing machine solving the problem in polynomial time.

The distinctive feature of NP problems is that they are difficult to find any solution for, but easy to check a proposed solution. As any problem in P can provide its own witness, i.e. a solution found in polynomial time is verified in polynomial time, it is obvious that P is in NP, i.e. P is a subset of NP.

Also notice that for an NP problem for which we can check a solution in polynomial time, we can find a solution in at most exponential time by checking all possible solutions.

There is a subtle point here. If the witness is to be checked by a Turing machine in polynomial time, it cannot grow in size faster than polynomial. Putting this another way, as the time to process the witness depends on its size, polynomial time implies polynomial growth in the size of the witness. If we write the witness in binary using m bits this has to be a polynomial in the problem size m=poly(n). Thus there can only be 2^m=2^poly(n) witnesses and each can be checked in polynomial time.

So solving the problem by checking every witness would take at most exponential time. That is, an NP problem is at most exponential to solve.

So we now have, writing Exp for the class of algorithms that take exponential time to solve:

P ⊆ NP ⊆ Exp

and we don't know if they are proper subsets of each other, i.e. does P=NP and NP=Exp?

The big question, and it is one of the $1 million Millennium prize questions, is whether P = NP:

Is it possible that there is a polynomial algorithm that solves problems that have a polynomial time verification.

Most computer scientists hold the opinion that this isn’t possible, i.e. P≠NP, but without a proof there is no certainty.

Co-NP

The complement of a decision problem is the same problem re-worded to swap the “yes” and “no” aspects of the decision, so “there is a subset that sums to zero” becomes “there is no subset that sums to zero”. If a decision problem is in NP then its complement is by definition in a class called co-NP. Just being in co-NP says nothing about whether or not there is a witness for the problem, just that there is a witness for the complement of the problem.

Another unsolved problem is whether NP=co-NP, that is, is every problem in co-NP also in NP and vice-versa. It is generally accepted that the two are not equal, that is there are problems in co-NP that are not in NP, but there is no proof of this as yet.

Consider the co-NP problem, “there is no subset that sums to zero”. How could you provide a witness of this? There is no point in offering up a subset that sums to a non-zero value as this counterexample doesn’t prove that there isn’t an alternative set that sums to zero. You might think at this point that NP ≠ co-NP is proved, but this is not proof.

There are examples of problems that were thought not to be in NP but later were proved to be in NP. For example, consider the problem of proving that a number x is composite, i.e. not a prime. To do this you need to test for all possible factors by dividing and in Chapter 15 this was stated to be O(2ⁿ) where n is the number of bits. However, you can provide a witness that x is composite by simply giving one of its factors. This can be verified in polynomial time and hence composite is in NP.

Now consider the complementary problem, given a number x prove that it is not composite i.e. it is a prime. This is in co-NP as it is the complement of a problem in NP.

Originally it was thought that there was no witness for primeness, but then one was found. This put prime testing in NP, which means composite as the complement of a problem in NP is in co-NP as well. As explained in Chapter 14, eventually prime testing was shown to be in P and hence so is composite testing.

Is there a witness for the complement subset sum problem? It seems unlikely, but who knows - perhaps there could be a bound on the size of sum obtainable from a set that makes a zero sum impossible. If it could be proved that no such witness existed, we would have the result NP ≠ co-NP.