What Is Computable?
Written by Mike James   
Article Index
What Is Computable?
NP and Non-Computable Problems
Non-Computable Numbers and Chaos

NP problems

It sounds as if this is the end of the story but the subject has much more subtlety than this!

For example, there are the NP – Nondeterministic Polynomical – problems. These are such that if you guess a solution then you can verify that it is a solution in polynomial time but if you don’t guess a solution then you can’t find one in polynomial time.

Such NP problems are ones that look difficult but seem to have a loop hole that makes them easier!

For example if you want to write a program that solve jigsaw puzzles then you have to face up to the fact that you are not going to find a general solution that takes time proportional to a polynomial in N, the number of pieces. In fact you can see that it is roughly N! and this increases faster than any polynomial in N.
(N! is N factorial, for example 4!=4x3x2x1)

Finding a solution to a jigsaw is difficult but if someone gives you a possible solution you can check that it is a solution by examining each of the pieces. That is, checking a solution takes time proportional to N and thus solving a jigsaw is an NP problem.

Another, perhaps more important example in this day of public key cryptography, is testing a number to see if it is a prime. To do this you have to test to see if the number is divisible by numbers smaller than it. In this case the measure of the work to be done, N, is the number of digits in the given number and testing it for divisibility by all of the values from 2 to its square root takes time that is exponential in the number of digits. On the other hand it you give me a potential factor and ask me to test that it divides then I can do this almost without effort! 

In this case the question “is this number a nonprime” is NP because it only takes a single divisor to prove that it isn’t. You can think of the divisor provided as a “certificate” that the number in question isn’t a prime. On the other hand the related, or “dual” question, “is this number a prime” cannot be solved by providing a certificate. The reason is that a prime is something that doesn’t have a divisor and it is difficult to see how you could provide a single piece of evidence that would allow this to be checked.

To this day no one knows if this problem is NP or not because there is the possibility that a certificate for “primeness” could exist.

Being complete

The great unsolved problem of algorithms remains to this day – can all NP problems be solved in polynomial time. Most people guess that the answer is no but so far there is still no proof of this and lots of theoreticians say that their hunch is that that answer is yes – the problems that look difficult really aren’t.

To make this task seem even easier there are some NP problems, NP Complete problems, which are representative of all NP problems in the sense that if you can solve one of them you can solve all of the NP problems. Believe it or not, even with all of the effort spent on trying to find a polynomial solution to an NP Complete problem, no solutions have been found and most computer scientists are of the opinion that no such solutions exist. 

Non-computable problems

If you think that NP problems are a little bit odd consider the simple fact that there are problems for which it can be proved that an algorithm of any sort cannot be found. These are not out of our reach because of resource limitations. They are out of our reach because the logic of the universe prohibits us from inventing an algorithm that works out the answer we seek. 

The best-known example involves the halting problem for a Turing machine but the type of computer doesn’t really matter.

The halting problem is easy to explain – simply write a program that examines other programs to determine if they halt or loop forever. Obviously whether or not a program halts depends on the data it is fed so in this case we mean program to be code plus the data it operates on. 

In other words we want a program that can read the code of any other program plus its data and work out if the process halts or loops forever. This sounds as though it should be possible if not easy - but it cannot be done.

The simple reason why this cannot be done is that the program you have invented is a program and you can feed it itself and ask the question does it halt. Yes this is another example of a self reference leading to problems.

From this stage it is easy enough to construct a paradox that if your program halts then it doesn’t and if it doesn’t then it does.

The details can be found in the books shown on the right among many others, but you can get the general idea from the following three diagrams:

 

halt1

It starts off innocently enough – just create a program that tells you if another program stops or loops forever when reading itself as input

 

halt2

A slight modification is to add a loop that never ends if the program being tested ends. So now you only see a message if the program being tested ends otherwise the modified halting test loops forever.

 

halt3

Now we hit the paradox. Feed the modified program complete with a test subject into itself. Now if it stops it doesn’t, but if it doesn’t it does!

There are a lot of technical details needed to make this argument water tight but this is the general idea. If you know some other paradoxes you will recognize it as a variation on the Barber and similar paradoxes. The Barber paradox is if the Barber in the town has to shave everyone who does not shave themselves - who shaves the Barber?  If the Barber does then he doesn't etc.

 
Banner
 

<ASIN:0465026567>



 
 

   
RSS feed of all content
I Programmer - full contents
Copyright © 2014 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.