In computer science, algorithmic computation ranges in a wide array of application including Databases, Query evaluation, Tree algorithms, mathematical computations, Sorting and searching algorithms and so on. The base of the theory is the limited space-time resource available to execute and solve a given problem majorly (but not limited to) when the problem class scales. For example, a query on a database would execute fine for a small set of data objects however when it grows to millions of records the same algorithm will face a time-space dilemma for computing the solution.
The root of this theory is deeply mathematical. Whenever a problem or an algorithm is evaluated, computing its complexity is critical for correct evaluation (or more importantly identify the scalability) of the algorithm.
For sake of clarity and ease problems are divided in various computational or complexity classes. This is mainly done to avoid going into the highly “scary” mathematical proof. The idea here is to relate a certain problem to another problem in the same class, just as we say phrases like “as cool as a cucumber” to relate.
Here’s a summary of a lecture I took last term that served as the primer to complexity classes that I always wanted to know.
Complexity Classes
A complexity class is a set of problems that can be solved with-in a certain amount of time-space resource. Problems that can be solved but lies in an impractical consumption of resource e.g. a database query taking 3 years to compute are called intractable problems.
P-TIME
P-TIME or Polynomial-Time is the class which is considered as the dividing boundary for the complexity classes. Problems that are solved in polynomial time i.e. O( nk ) lies in this class. The divide for the complexity classes using P-TIME can be established as:
- Inside P-TIME (practical solution exists – tractable)
- Beyond P-TIME (unlikely that an efficient algorithm exists but nevertheless may be possible)
- Far from P-TIME (proven that all solutions are intractable)
Inside P-TIME
The problems in this class are found to have very efficient and effective (in most cases parallel) solutions and algorithms. Any room for further efficiency is extremely unlikely for such algorithms. The problems are solved in polynomial linear time e.g. with-in Circuit time (AC0), Counting Gates (TC0), parallel (NC1) and O(log n).
Beyond P-TIME
P-TIME: Like discussed earlier, the problem can be solved in polynomial time.
P-SPACE: A problem can be solved by consuming memory in polynomial “space”.
NP:
Non-deterministic polynomial time. The solution of the problem can not be found however if a solution is known it can be verified to be correct in polynomial time. For example: Finding all prime numbers up to a very large number versus verifying whether a very large number is prime or not. Or even the infamous travelling salesman problem.
coNP:
It is also dubbed as the complement of NP, which means that a given set of “candidates” can be identified as “possible solutions” to a given problem.
The further problems go beyond PTIME, the chances of efficient algorithm (and thus solution) plummets considerably.
COMPLETE-ness
Often when one is doing algorithmic complexity exercises, he will come across solutions that lie in NP-COMPLETE or PSPACE-COMPLETE classes. These set of problems in a given class are supposed to be the hardest problems in these sets. It will be very hard to find a solution in lower complexity for COMPLETE problems.
Un-answered Complexity Question: P=NP?
The Millenium prize problem which remains unsolved even today is to prove whether Polynomial time problems are equivalent to the non-deterministic polynomial time problems. The first person to solve or propose a solution will be a $1 million reward. Anyway, the important point here is that should this be proved many computational problems in higher complexity class of NP will be reduced to P-Time problems with very efficient algorithms.
[ The above extracts and concepts are taken from Prof. Libkin’s lecture on complexity classes and recorded here for my own sake and for those who always wanted to have “an easy primer” to complexity classes. ]
