Complexity Theory - Part 2

In the previous part, we have seen the basics we formed to go ahead to taste the actual spice of the dish, called “Complexity Theory”. So far what we have done is that we have gathered the ingredients. Now is the time for the actual cooking. So let us turn on the stove, and see the dish getting cooked.

The previous part can be visited on:

Complexity Theory — part 1

Polynomial Verification:

We define a verification algorithm as being a two-argument algorithm A, where one argument is an ordinary input string x and the other is a binary string y called a certificate. So algorithm A verifies x if A(x, y) = 1.

The language verified by the algorithm A is:

L = {x ϵ {0, 1}*: there exists y ϵ {0, 1}* such that A(x, y) = 1}

Let us talk about this informally. Now consider the “Sum of Subsets” problem. We have an array of numbers, we have a target number. Our goal is to find out the subset of that array such that the sum of the numbers in that subset is equal to the target.

Assume someone solved the problem on paper and handed over the solution to you. Let us not keep blind faith in him and check whether the solution he gave is right or not. I have a doubt and I check two things: Firstly, the numbers should exist in the original array. Secondly, the numbers in the subset add up to the target element, and the solver has not bluffed. So this checking done with the proper steps becomes our verification algorithm.

Translating to the formal definition, let me keep x as the string which tells which elements are included, for example, x = 111000 tells me that elements of index 0, 1, and 2 are added in the subset. Let y be the binary representation of the target number, so for target = 20, y = 10100. So if my solution is right, my verification algorithm A will give me A(111000, 10100) = 1.

NP:

The complexity class NP is the class of languages that can be verified by a polynomial-time algorithm.

A language L belongs to L if and only if there exists a two-input polynomial-time algorithm A and constant c such that:

L = {x ϵ {0, 1}*: there exists a certificate y with |y| = O(|x|ᶜ) such that A(x, y) = 1}

We say that algorithm A verifies L in polynomial time.

Let us revisit the “Sum of Subset” problem. What my verification algorithm A can do is that it just goes traverses in x. It then checks whether it is 0 or 1. If it is 1, it is added. We then check the added total with the target. If it matches, return 1, else return 0. That’s it!! Our solution is verified.

Now let me raise this question. Is the complexity of A polynomial? The answer is “yes”. A is a polynomial-time algorithm. So we verified the language

L = {x ϵ {0, 1}*: there exists y ϵ {0, 1}* such that a subset of the array adds up to the decimal value of y and x represents which element is included in the subset}

in polynomial time. So we say that L belongs to the complexity class NP.

So similarly, any superpolynomial time algorithm which can be verified in polynomial time comes in NP. Similarly, any polynomial-time algorithm which is verified in polynomial time comes in NP. In general, finding out the solution is more complex than verifying the solution, since we know what we want in the solution. So it is evident that any language in P will be verified in polynomial time. Hence we conclude that “P belongs to NP”.

Reducibility:

A language L₁ is polynomial-time reducible to a language L₂, written L₁ ≥ₚ L₂, if there exists a polynomial-time computable function f: {0, 1}* → {0, 1}*, such that for all x ϵ {0, 1}*, x ϵ L₁ if and only if f(x) ϵ L₂.

f is called the reduction function and a polynomial-time algorithm F that computes f is called the reduction algorithm.

Let L₁ = {x ϵ {0, 1}*: decimal value of x is a whole number}

Let L₂ = {x ϵ {0, 1}*: decimal value of x is an even whole number}

In binary, as referred to in the previous part, the decimal value of a number can be doubled just by appending a 0 in the actual string. Also, every doubled number is always even. Now I can reduce L₁ to L₂ simply by appending a 0. So my f will be:

f(x) = x + “0”

For all x ϵ L₁, f(x) ϵ L₂. So we say that L₁ ≥ₚ L₂ since F for f is a polynomial-time algorithm.

NP-Completeness:

If I say L₁ ≥ₚ L₂, I can also say that L₁ is not more than a polynomial factor harder than L₂.

A language L is NP-complete if

1. L ϵ NP

2. L’ ≥ₚ L, for all L ϵ NP

We realize from this definition that NP-complete problems are the hardest problems in NP.

If property 2 is satisfied, but not property 1, we say that the language is “NP-Hard”.

Graphical representation of the complexity classes

Procedure for proof:

By reducing a known NP-complete language L’ to L, we implicitly reduce every language in NP to L. With this, we can prove the NP-completeness for any other language.

1. Prove L ϵ NP.
2. Select a known NP-complete language L’.
3. Describe an algorithm that computes a function f mapping every instance x ϵ {0, 1}* of L’ to an instance f(x) of L.
4. Prove that the function f satisfies x ϵ L’ iff f(x) ϵ L for all x ϵ {0,1}*.
5. Prove that the algorithm computing f runs in polynomial time.

Decision vs Optimization Problems:

NP-completeness applies to the realm of decision problems. It was set up this way because it’s easier to compare the difficulty of decision problems than that of optimization problems.

If we take any optimization problem, verifying the solution of the problem involves solving the problem all over again. This will not give us any idea whether the algorithm for the problem can be optimized in the future.

So a way to include any optimization problem into such a discussion is to convert an optimization problem into a decision problem. Just to tell you, decision problems output a “yes” or a “no”, while optimization problems output an optimum value specific to the problem.

Let us consider the problem “Travelling Salesman” problem. This gives us the minimum distance covered such that all the destinations are visited, and you’re back to the source. To convert into a decision problem, we just make the algorithm answer this question, “Is my minimum distance covered less than ‘X’ units?”, where X is some number. Based on whether the answer is “yes” or “no”, I will change the value for X. Let’s say the value is 9. I can start with X as, say 20. I will get the answer “yes”. So I will reduce X to, say 10. My answer will still be “yes”. I will again reduce it to, say 5. My answer will be “no” this time. Let me raise X to 7. Again a “no”. So similarly I will go up and down depending on what output I got from the algorithm.

References:

T. Cormen, Charles E. Leiserson and Ronald D River, Introduction to Algorithms, PHI, 3 rd edition, 2009.

NP-Completeness | Set 1 (Introduction) - GeeksforGeeks