The term 'Computer Science' for many people might bring up the imagery of people working on obscure code, or some automated robots and some other really fancy stuff. As a wannabe-theoretician, I claim that a large part of Computer Science has very little to do with "computers" as we know them. In this blog, I will introduce a fascinating field of Computer Science known as Computational Complexity. My aim would be to address extremely deep questions at the same time I would want the target readers of this post to be as wide as possible - i.e. I would hope that any person even without a formal training in science should be able to understand these questions.
The hardness of a problem
The principal aim of Computational Complexity is to study the 'hardness' of a problem. The 'hardness' of a problem is - how difficult is it to solve a particular problem. Computational Complexity aims to quantify how difficult or easy a particular problem is. Today we will measure hardness in terms of the amount of time one would need to solve the problem. This is not the only measure of complexity that is studied. There is also a notion of 'Space Complexity', which I will not discuss today. Quantifying the difficulty of a problem might seem rather unintuitive. A reader might think - the difficulty of a problem depends on the person (or the computer system) which is trying to solve this problem. Although that's correct, the aim is to classify problems such that the classification holds irrespective of who is solving the problem. It is done in the following manner. If a problem A is classified to be harder than B, then A will take more time than B irrespective of who is solving it. (Let me warn you, this is a rather informal way of saying it - I'll be formalising it in the later paragraphs).
Reductions
In this section, we will talk about a very interesting concept of Complexity Theory called reductions. We say that if a problem A can be reduced to B, then a solution to B in time T would guarantee us a solution to A time less than or equal to T. In other words, B is at least as hard as A. I would like to now give a concrete example. This would involve some amount of mathematics, which cannot be avoided. Let's define the following two problems:
- KNAPSACK: Suppose that you are planning an air-travel. There are a bunch of items you would like to take with you. You know that weight of each item and you can quantify the value of each item. The airline has a weight limit of K. The question we ask is - 'Is it possible for us to fill up our bag with items such that the total value of items is V while we are within the weight limit.
- SUBSET-SUM: We are given a set S of numbers. We are given a number Y. The question is does there exist a subset of S, such that the numbers in S sum to Y.
Notice that the SUBSET-SUM is a special case of KNAPSACK. Hence a solution to KNAPSACK will give us a solution to the SUBSET-SUM. We can thus claim that SUBSET-SUM can be thus reduced to KNAPSACK. In fact, these problems are so-called NP-Hard problems. Which means they are the hardest problems in the class NP (I will tell you about it in the next section). What is remarkable about these problems is that there are a whole bunch of famous problems (one problem that you might have seen is the SUDOKU) which are NP-Hard. Thus it means that problems like KNAPSACK and SUBSET-SUM can be reduced to SUDOKU. Which essentially means that solving SUDOKU is equivalent to solving KNAPSACK or SUBSET-SUM! Is it not remarkable?
Our two important Complexity Classes
Now we define the two famous complexity classes P and NP. Before we do that we will need the notion of a Polynomial Time Algorithm. If you are not really aware of what it is - think about 'polynomial time' as a reasonable amount of time. Formally speaking 'polynomial time' refers to time which is a polynomial in the input size.
Class P: It is a set of all decision problems (problems which can be answered as YES or NO), for which there exists a polynomial time algorithm.
Class NP: It is a set of all decision problems for which given a certificate of the solution, the solution can be verified in polynomial time.
Clearly, if a problem is in P, it is also in NP. If you can find a solution - you can also verify it! The million dollar question (literally million dollars) is does it also hold in the opposite direction? If we know that the solution to a problem can be verified in polynomial time, does it mean that we can also find it polynomial time? This is probably the most famous question in Computer Science - It is the so-called P=NP problem.
What do P and NP stand for?
P stands for polynomial time. Some of you may guess that NP could stand for non-polynomial time. However, that is not true. NP, in fact, stands for non-deterministic polynomial time. This nomenclature comes from other equivalent definitions of these classes which are based on Turing Machines which we have not discussed in this post.
I will end this post here. In the next post, I will talk about Turing Machines. Please let me know what you think about this blog in the comments section below!
No comments:
Post a Comment