Reasoning about what computers
can and cannot do
CS258 Computer Theory Paper - 1998
Written By:
Lucas Modrich
Tutor:
Table of Contents
Computers have come a long way since their emergence into the mainstream market in the form of a desktop PC. Since the early days of computers people have been testing their limits, pushing them further and further, in an attempt to find out just how much they can actually do.
These days it is realized that computers, despite the misconception that many people have, cannot do everything. Problems that come under the general areas of cryptography, and complexity, are where computers seem to have the most difficulty in solving problems. This in some cases may be a disadvantage, but it can also be the fact that an algorithm is based on, in the case of cryptography.
What I intend to discuss in this paper is not so much, generally what computers can and can't do, but more so what they can and can't do in relation to complexity, cryptography., and grammars. These areas are some of the most troubling areas for computers as far as their ability to solve problems from within these domains.
Complexity by definition is something consisting of several parts, or that is in some way complicated. Computers can perform extremely complex operations on vast quantities of information, in very little time, in comparison to a human. But some tasks are simple beyond their ability to solve in any reasonable amount of time. Even with the most efficient algorithm available and the fastest computers in the world, some problems couldn't be solved in billions of years.
The complexity of an algorithm is the only fact in determining weather a problem is tractable or intractable. Algorithm complexity has it's own notation, known as 'Big O' notation. Big O notation is simply a way of expressing the algorithms complexity, in terms of rate of growth of the time taken to complete the most complex part of the algorithm.
Rates Of Growth
| n | log n | n2 | 2n | n! |
|---|---|---|---|---|
| 5 | 2 | 25 | 32 | 120 |
| 10 | 3 | 100 | 1024 | 3628800 |
| 20 | 4 | 400 | 1048576 | ~1018 |
| 30 | 4 | 900 | ~109 | ~1032 |
| 40 | 5 | 1600 | ~1012 | ~1048 |
| 50 | 5 | 2500 | ~1015 | ~1064 |
| 100 | 6 | 10000 | ~1030 | ~10161 |
| 200 | 7 | 40000 | ~1060 | ~10374 |
Basically there are two general types of problem, those in P (Polynomial-time), which are said to be tractable, and those in NP (Nondeterministic Polynomial-time), which are a subset of intractable problems.
An algorithms complexity is taken from the most efficient solution to the problem. So for example, if a problem has both a liner and a polynomial solution then the solution is said to be linear as it is the most efficient. Generally if a problem is solvable in polynomial (nr) time or less then it is said to be tractable and is classed as being within P , anything above polynomial time is said to be generally intractable and classed as being within NP.
Problems can also be undecidable. This is when it has actually been proven that no one could actually come up with an algorithm to solve it. An example of an unsolvable problem is one known as 'The Tiling Problem'.
Some intractable problems may appear as though they are impossible, but given enough time, they are actually solvable. Intractable problems are called such as they, in most cases will take far to long to solve for the importance of the information that it will retrieve. This is an important fact that is used in cryptography. Most cryptographic techniques, rely heavily on this fact.
Much of the reason for algorithms being extremely complex is due to the large number of different solutions to the problem. A lot of the algorithms time is spent searching for a solution.
The class of problem known as NP, also contain another class of problem called NP-complete problems. These are the hardest of all the problems. They have some interesting properties though. For every NP-complete problem there are polynomial-time reductions from all of the other NP-complete problems. If an easy solution, one in polynomial-time, is found to any one of the NP-complete problems then this solution can be mapped to every other problem in NP. This can be done in polynomial-time, as well solved in polynomial-time.
As NP-complete problems are within the class of NP problems they are also believed to be intractable, but no has actually proven that they aren't tractable.
Cryptography has been around in it's various forms for centuries. Most likely originating from some wartime development, in the need to conceal a message from the enemy, and to only be readable by those parties that the message was intended for.
Cryptography has come a long way, and has developed quite dramatically from the primitive cyphers that were used centuries ago. The area has a large mathematical content now, as it is now necessary to have an encryption system that is safe well into the foreseeable future.
With the development of computers, cryptography has grown rapidly, with computers being the ideal area for furthering it's development. The use of computers abilities and their downfalls makes them perfect for cryptography. They are able to process large quantities of data, but unable to solve many NP problems in any reasonable time.
Because of this most cryptographic systems are based on NP problems. This is due to the properties that NP problems have. They can be checked in polynomial time, but not solved.
In basic crypto-systems, such as where a password, or pin needs to be encrypted, there is an alphabet which the user can choose their pin from, and also a required length for the pin. When dealing with simplistic encryption methods, it has been found that the length of the pin to be encrypted is the most important part in increasing the difficulty of cracking it. Although the alphabet does have an effect on the time it will take to crack the length has a much greater impact. For example, a pin that comes from the alphabet a-z and contains 4 characters, is far less safe that one that comes from the alphabet a-g with 20 characters.
One of the most common and widely used types of crypto-systems available today are those that use a public key system. Public key crypto-systems are a fairly popular type of encryption system due to the properties that they have. The properties that a public key crypto-system have are:
Public Key - E
Private Key - D
E not easily derivable from D
Finding E(m) (Encryption of message m) can be done easily
For this to be possible, E(m) must be a one-way function.
Because of its properties, this type of crypto-system allows us to perform many types of encryption. We can simply encrypt and decrypt but we can also sign, and verify the origin of a message.
For the signing and verification the crypto-system is required to support the following:
RSA is a form of public key system that is widely used and respected. It produces a key set by a mathematical process involving two large prime numbers.
So from the generation of keys by the above method, in order to break an encrypted message, it would be necessary to find d from the public key containing e and c. If we are able to factor c into the two primes a and b, we can easily find d from e, a and b. So the system depends on the fact that c can't be, or is extremely hard to, factor in any reasonable amount of time. So the choice of large primes increases the the size of c, and also increases the difficulty, and time needed to factor it, which in turn increases the security of the system.
The fact that factoring is know to be an intractable problem, as it is an NP problem, determines that it is fairly unlikely that a quick algorithm will be found to perform the task. The problem of finding large prime to use with the system can be overcome through the use of probabilistic algorithms, which will allow the primes to be easily found, so the system can be developed in a reasonable amount of time.
An example of how the RSA Public Key crypto-system works.
When the complexity of an algorithm becomes so great that it is intractable, then in order to solve the problem it would take more time than is realistic to spend finding a solution. The development of probabilistic algorithms have helped in this area. A probabilistic algorithm will perform the required task, in tractable time, but only with a certain percentage of accuracy, but generally high enough to be useable for problems needs.
When locating large prime numbers for use with the RSA crypto-system, it would be intractable to generate a number then factor in all number between 2 and n-1 in order to find if it were prime. So a probabilistic algorithm is used. This algorithm would look similar to this:
The algorithm must be told how to choose the values of i, as they must be chosen carefully in order to ensure a high degree of probabilistic correctness.
The definition of a grammar is the study of the rules of a specified language, or a means of showing relation between words. When we define a grammar to give a computer, these are the types of things that we are wanting to achieve. A grammar can be defined for many different cases, but all have the one simple (not always so simple to implement) purpose, to give the computer some way of being able to check if a given phrase is valid for the language that the grammar defines.
The grammar gives the computer the ability to parse through and check for any invalid strings within the phrase. The grammar must be defined in such a way that all phrases that are physically possible to create according to the rules of the language are able to be generated by the grammar.
Even though a grammar that is given to a computer, defines the rules, strictly, of how to construct, and interpret a specific language, the computer still has no understanding of what the language is, or what it means.
The grammar could check if what the user has typed is correct, according to the rules of the grammar, and validate it, but it wouldn't understand even the most simplistic sentence. No matter how well the grammar is defined, how simple the language is, or even how goo the computer is, the computer will never be able to understand the phrase.