Computability and Complexity

Introduction to Computation Complex Theory

Broad Overview :

Complexity theory, in a nutshell, a complexity word is a quite fancy word, literally, it sounds complex, but it is not an intimidating topic. What it really means is analyzing the program or we can say analyzing the efficiency of the program, figuring out whether the program is correct, figuring out whether one program is better than the other program and how exactly do we go about doing it in a very quantified way. There are lots of variants of this bit that we are generally looking at when we are doing any computer programming or in general or in most practical purposes are just two main complexities, one is Time Complexity, and the other is Space (memory) Complexity.Time complexity is simple as how fast your code runs, how much time it will take, depends on the number of steps. Time complexity is hardware-independent, so let suppose I write one program, and I might have a supercomputer or I might have a simple laptop, so the time will be different based on where you run the program so it is not a very deterministic metric and we want something very robust and pretty deterministic so next we have a very simple step, which does not measure the actual time but we know that the time is basically very proportional to the number of steps that are taken by the program.

Example of Complexity in Time (execution) and Space (memory) factors :

Example-1 : More Complex

i = 1;                                                1s
while( i <= 10 )                              11s
{
    a = 5;                                           10s
    result = i * a;                              10s
    printf(“\n” /d”, result);            10s
    i++;                                               10s
}

Here, we assume each variable is equal to 2 Bytes. In the above example we use three variables (i, a, result) which is 6 Bytes.

Execution Time : 52s

Memory (Space) : 6 Bytes

Example-2 : Less Complex

a = 5;                                                      1s
i = 1;                                                       1s
while( i<=10)                                        11s
{  
    result = i * a;                                    10s
    printf(“\n” /d”, result);                  10s
    i++;                                                     10s 
}

Execution Time : 43s

Memory (Space) : 6 Bytes

Problems in Computation Complexity :

• Solvable Problems :
  A problem is said to be solvable first either if you find a solution means what there exists a potential solution, you have an algorithm and procedure to find its solution but also the problem is solvable if you proved mathematically there exists no solution which means the problem does not require any further discussion because we know the problem can never be solvable n matter how many times, we try to solve the problem.
• Unsolvable Problem :
  Unsolvable problems in computer science is a temporary status of the problem because a problem is unsolvable, we say that instant of time neither we are able to solve the problem nor in a position to say that the problem can not be solved which means in unsolvable problems we are still confused, and the discussion is still open. And if the problem lies in this domain so it is known as an unsolvable problem.
• Decidable Vs Undecidable:
  Basically, the solvable problems are divided into two categories – Decidable and Undecidable. Before going into the depth of the decidability domain, we should have a good knowledge of algorithms and machine models of the Theory of computation, especially the Turing Machines.
• Decidable Problem :
  When we talk about the decidable problems the two important terms are used algorithms and procedures. The procedure is a step-by-step instruction to solve a problem. A procedure becomes an algorithm when we say what is the approximate time to solve a problem. When we are concern with decidable problems means it includes both algorithms as well as procedures.
• Undecidable Problem :
  When we talk about undecidable problems then we can not predict the time of the problem in which a problem can be solved. Undecidable problems are also solvable and there exists a procedure to solve the problem, but the problem is complex as we cannot predict the approximate time.

Computable and non-computable problems in TOC

Computable Problems –

You are familiar with many problems (or functions) that are computable (or decidable), meaning there exists some algorithm that computes an answer (or output) to any instance of the problem (or for any input to the function) in a finite number of simple steps.A simple example is the integer increment operation:

f(x) = x + 1 

It should be intuitive that given any integer x, we can compute x + 1 in a finite number of steps. Since x is finite, it may be represented by a finite string of digits. Using the addition method (or algorithm) we all learned in school, we can clearly compute another string of digits representing the integer equivalent to x + 1.

Yet there are also problems and functions that that are non-computable (or undecidable or uncomputable), meaning that there exists no algorithm that can compute an answer or output for all inputs in a finite number of simple steps. (Undecidable simply means non-computable in the context of a decision problem, whose answer (or output) is either “true” or “false”).

Non-Computable Problems –

A non-computable is a problem for which there is no algorithm that can be used to solve it. Most famous example of a non-computablity (or undecidability) is the Halting Problem. Given a description of a Turing Machine and its initial input, determine whether the program, when executed on this input, ever halts (completes).

The alternative is that it runs forever without halting. The halting problem is about seeing if a machine will ever come to a halt when a certain input is given to it or if it will finish running. This input itself can be something that keeps calling itself forever which means that it will cause the program to run forever.

Other example of an uncomputable problem is: determining whether a computer program loops forever on some input. You can replace “computer program” by “Turing machine or algorithm”if you know about Turing machine.

Proving Computability or Non-Computability –

We can show that a problem is computable by describing a procedure and proving that the procedure always terminates and always produces the correct answer. It is enough to provide a convincing argument that such a procedure exists finding the actual procedure is not necessary (but often helps to make the argument more convincing).

To show that a problem is not computable, we need to show that no algorithm exists that solves the problem. Since there are an infinite number of possible procedures, we cannot just list all possible procedures and show why each one does not solve the problem. Instead, we need to construct an argument showing that if there were such an algorithm it would lead to a contradiction.

The core of our argument is based on knowing the Halting Problem is noncom- putable. If a solution to some new problem P could be used to solve the Halting Problem, then we know that P is also noncomputable. That is, no algorithm exists that can solve P since if such an algorithm exists it could be used to also solve the Halting Problem which we already know is impossible.The proof technique where we show that a solution for some problem P can be used to solve a different problem Q is known as a reduction.A problem Q is reducible to a problem P if a solution to P could be used to solve Q. This means that problem Q is no harder than problem P, since a solution to problem Q leads to a solution to problem P.

Some Examples of Computable Problems –

These are four simple examples of computable problem:

1. Computing the greatest common divisor of a pair of integers.
2. Computing the least common multiple of a pair of integers.
3. Finding the shortest path between a pair of nodes in a finite graph.
4. Determining whether a propositional formula is a tautology.

Some Examples On Computable Problems – State Entry Problem.

Consider the problem of determining if a string ‘w’ is given to some Turing machine ‘M’ will it enter some state ‘q'(where q belongs to set of all states in Turing machine M and string w is not equal to empty string). Is it computable or non-computable?

Explanation –

We show the State Entry Problem is non-computable by showing that it is as hard as the Halting Problem, which we already know is non-computable.

State Entry Problem is asking us on given string w if we start from initial state of Turing machine will it reach to a state q. Now this state entry problem can be converted to halting problem. Halting problem is whether our Turing machine ever halts and state entry problem is asking same thing whether this Turing machine halts at some state q, if we give string w as input to the Turing machine M. So the state entry problem, is non-computable as we converted it to halting problem which we already know is non-computable problem. So in this way, we can prove non-computability.