Explaining Time Complexity and NP Problems

[evinda]

Hello! (Wave)

I want to choose if the following sentences are true or false and justify the reason for the choice.

• Polynomial: good, exponential: bad.
• Radix Sort works correctly if we use any right sorting algorithm to sort each digit.
• Given an array $A[1 \dots n]$ from integers, the time that [m] CountingSort [/m] requires is polynomial in relation to the input size $n$.
• Given an array $A[1 \dots n]$ from integers, the time that [m] HeapSort [/m] requires is polynomial in relation to the input size $n$.
• For a Dynamic Programming algorithm, the calculation of all the values with bottom-up is asymptotically faster than the use of recursion and memoization.
• The time of a dynamic algorithm is always $O(P)$ where $P$ is the number of subproblems.
• Each problem that belongs to [m]ΝΡ[/m] is solved in exponential time.

• This sentence is true. But how could we explain why it is actually like that? (Thinking)
• False. We can only use a sorting algorithm, if it is stable.
• Right. The [m] CountingSort [/m] is a linear algorithm.
• False. [m] HeapSort [/m] requires $O(n \log n)$ time.
• False. The calculation of all the values with bottom-up is asymptotically the same as if we use recursion and memoization.
  Do I have to explain why the above four properties hold further? If so, what could we add?
• How could we deterine if this is true or not?
• The [m] NP [/m] problems cannot be solved in polynomial time, right? But do we know that all these problems are solved in exponential time?
  

 

[Nono713]

The NP problems cannot be solved in polynomial time, right? But do we know that all these problems are solved in exponential time?

Did you forget the definition of the NP complexity class? Because this is completely wrong. Hint: any problem in P is also in NP.

 

[evinda]

Did you forget the definition of the NP complexity class? Because this is completely wrong. Hint: any problem in P is also in NP.

We define [m] NP [/m]( for nondeterministic polynomial ) to be the class of all languages that are decided by a polynomially bounded nondeterministic Turing machine.Do you mean the above definition? (Thinking)

 

[Nono713]

We define [m] NP [/m]( for nondeterministic polynomial ) to be the class of all languages that are decided by a polynomially bounded nondeterministic Turing machine.Do you mean the above definition? (Thinking)

Yes.. that easily implies that any problem in P is also in NP. So...

 

[evinda]

Yes.. that easily implies that any problem in P is also in NP. So...

So because of the fact that the [m] NP [/m] problems can be solved in polynomial time, with the use of a Turing machine we deduce that the proposition is right? (Thinking)

Or have I understood it wrong?

 

[Nono713]

So because of the fact that the [m] NP [/m] problems can be solved in polynomial time, with the use of a Turing machine we deduce that the proposition is right? (Thinking)

Or have I understood it wrong?

Who said any NP problem can be solved in polynomial time? P is in NP, but it's not known whether NP is in P (i.e. whether P = NP). What it does mean, however, forgetting Turing Machines for now, is that any problem admitting a polynomial-time algorithm that solves it is in P and therefore also in NP. So take your favorite P problem (for instance, finding the maximum element in an array). This problem is in P, and therefore it is also in NP, but it can be solved in polynomial time, contradicting the proposition, and so the proposition is wrong. Does that make sense?

(unless the proposition meant "at most in exponential time"?)

 

[evinda]

Who said any NP problem can be solved in polynomial time? P is in NP, but it's not known whether NP is in P (i.e. whether P = NP). What it does mean, however, forgetting Turing Machines for now, is that any problem admitting a polynomial-time algorithm that solves it is in P and therefore also in NP. So take your favorite P problem (for instance, finding the maximum element in an array). This problem is in P, and therefore it is also in NP, but it can be solved in polynomial time, contradicting the proposition, and so the proposition is wrong. Does that make sense?

(unless the proposition meant "at most in exponential time"?)

So does this mean that the problems that are in [m] P [/m] are a subset of the problems that are in [m] NP [/m]?
If so, could you explain me further why this holds?

 

[Nono713]

So does this mean that the problems that are in [m] P [/m] are a subset of the problems that are in [m] NP [/m]?
If so, could you explain me further why this holds?

Yes, $\mathrm{P} \subset \mathrm{NP}$. This holds because as we know, NP can be defined as the class of problems which can be solved in polynomial time by a nondeterministic Turing machine (or languages that can be accepted, or whatever your preferred theoretical definition is), while P can be defined as the class of problems that can be solved in polynomial time by a deterministic Turing machine. And a deterministic Turing machine is just a nondeterministic Turing machine that happens to not make any nondeterministic choices [just like an integer can be viewed as a real number that happens to have no fractional part]. In other words, any DTM is an NTM, and from that it follows that P is in NP.

Or, more loosely and directly, "if it is easy to find the solution to a problem, then it is also easy to verify any particular solution" (e.g. by simply solving it in polynomial time and comparing).

The most important thing to remember is that NP does NOT stand for "non-polynomial time", which is a very common misconception. It stands for NONDETERMINISTIC polynomial time which is completely different.

 

[evinda]

Yes, $\mathrm{P} \subset \mathrm{NP}$. This holds because as we know, NP can be defined as the class of problems which can be solved in polynomial time by a nondeterministic Turing machine (or languages that can be accepted, or whatever your preferred theoretical definition is), while P can be defined as the class of problems that can be solved in polynomial time by a deterministic Turing machine.

So does this mean that all the problems in NP can be solved in polynomial time by a nondeterministic Turing machine? (Thinking)

• Polynomial: good, exponential: bad.

Could we explain that the proposition is right as follows?

Suppose that we have an input of $n$ elements and want to run algorithm so that we will get an information about these $n$ elements. If the algorithm runs in polynomial time, the algorithm will finish in a reasonable time.
If, however, the algorithm is exponential, it will need a lot more time to calculate the result.

• For a Dynamic Programming algorithm, the calculation of all the values with bottom-up is asymptotically faster than the use of recursion and memoization.
• The time of a dynamic algorithm is always $O(P)$ where $P$ is the number of subproblems.

How could we determine if the above propositions hold or not?

 

[Nono713]

So does this mean that all the problems in NP can be solved in polynomial time by a nondeterministic Turing machine? (Thinking)

Yes. Of course, one cannot build a nondeterministic Turing machine (you might think of it as akin to predicting the future) so it's just a theoretical framework to understand complexity.

• Polynomial: good, exponential: bad.

Could we explain that the proposition is right as follows?

Suppose that we have an input of $n$ elements and want to run algorithm so that we will get an information about these $n$ elements. If the algorithm runs in polynomial time, the algorithm will finish in a reasonable time.
If, however, the algorithm is exponential, it will need a lot more time to calculate the result.

You're not really saying much here, you're just repeating the question... polynomial, good, "finish in reasonable time", exponential, bad, "need a lot more time"... this is all pretty vague, don't you think? Why polynomial and exponential specifically? What can you say about their growth?

For a Dynamic Programming algorithm, the calculation of all the values with bottom-up is asymptotically faster than the use of recursion and memoization.

I'm not an expert in dynamic algorithms but think about what it means to calculate the values (= solutions to subproblems) bottom-up? Doesn't that mean that each subproblem builds on already computed subproblems, and so doesn't need to solve them again each time? On the other hand, recursion is top-down, but what is the defining property of memoization? Conclude... maybe try to visualize it with a simple dynamic programming algorithm of your choice, with a tree of the subproblems.

 

[evinda]

Yes. Of course, one cannot build a nondeterministic Turing machine (you might think of it as akin to predicting the future) so it's just a theoretical framework to understand complexity.

Thinking bout it again... the NP-complete problems are also in NP and there is no known way to solve them in deterministic polynomial time...
But since the worst case is that an algorithm is exponential, can't we say that each problem in NP is solved in polynomial time? (Thinking)

You're not really saying much here, you're just repeating the question... polynomial, good, "finish in reasonable time", exponential, bad, "need a lot more time"... this is all pretty vague, don't you think? Why polynomial and exponential specifically? What can you say about their growth?

You mean that we have to justify the correctness of the proposition, saying that $O(n^a)=O(b^m), n,m,a,b \in \mathbb{N}$ ?

I'm not an expert in dynamic algorithms but think about what it means to calculate the values (= solutions to subproblems) bottom-up? Doesn't that mean that each subproblem builds on already computed subproblems, and so doesn't need to solve them again each time? On the other hand, recursion is top-down, but what is the defining property of memoization? Conclude... maybe try to visualize it with a simple dynamic programming algorithm of your choice, with a tree of the subproblems.

I thought that with bottom-up we start from the computation of the smallest subproblem, which we will need for the computation of the greater ones... At recursion, we start from the greater problems and in order to calculate them, we find the smaller ones..
Does it hold that each subproblem builds on already computed subproblems, and so doesn't need to solve them again each time in both cases? (Thinking)

 

[Nono713]

Thinking bout it again... the NP-complete problems are also in NP and there is no known way to solve them in deterministic polynomial time...
But since the worst case is that an algorithm is exponential, can't we say that each problem in NP is solved in polynomial time? (Thinking)

?

You mean that we have to justify the correctness of the proposition, saying that $O(n^a)=O(b^m), n,m,a,b \in \mathbb{N}$ ?

How are these two sets equal?! Anyway for the question I was thinking more about something along the lines of Cobham's thesis, if you have access to it (via your university or wherever) I think it would be a good read.

I thought that with bottom-up we start from the computation of the smallest subproblem, which we will need for the computation of the greater ones... At recursion, we start from the greater problems and in order to calculate them, we find the smaller ones..
Does it hold that each subproblem builds on already computed subproblems, and so doesn't need to solve them again each time in both cases? (Thinking)

Yes, with memoization the two techniques are actually equivalent (they compute the same things), I believe. I could be wrong, though.

 

[evinda]

?

I thought that it isn't known whether the NP-complete problems can be solved in polynomial time using a non-deterministic Turing machine... And aren't these problems also in NP?

Or am I wrong?

How are these two sets equal?! Anyway for the question I was thinking more about something along the lines of Cobham's thesis, if you have access to it (via your university or wherever) I think it would be a good read.

Oh, yes... They cannot be equal... But it holds that $O(n^a) \subset O(b^m)$, right?
I haven't heard of it... What is it about?

Yes, with memoization the two techniques are actually equivalent (they compute the same things), I believe. I could be wrong, though.

So, the time complexity is asymptotically the same, right?

 

[Nono713]

I thought that it isn't known whether the NP-complete problems can be solved in polynomial time using a non-deterministic Turing machine... And aren't these problems also in NP?

Or am I wrong?

NP-complete is a subset of NP (NP-complete is the intersection of NP and NP-hard). Therefore they can be solved in polynomial-time using a nondeterministic Turing machine. NP *stands for* nondeterministic polynomial time. Again, nondeterministic Turing machines cannot be built, so that doesn't mean all NP problems are easy to solve, of course.

If you are trying to get a handle on the "real" complexity of a problem, it's easier to think of it in terms of being able to verify the solution to a problem in polynomial time (for NP problems) by a deterministic Turing machine. It's the same thing, just from a different perspective (the two definitions are equivalent).

Oh, yes... They cannot be equal... But it holds that $O(n^a) \subset O(b^m)$, right?
I haven't heard of it... What is it about?

It introduces the P complexity class, and why polynomial time is a good way to classify "easy" problems. If you can read the paper (it's not publicly available it seems) you should. Most universities provide free access to publications behind paywalls even to undergraduates, I believe. From http://en.wikipedia.org/wiki/Cobham%27s_thesis:

Cobham's thesis, also known as Cobham–Edmonds thesis (named after Alan Cobham and Jack Edmonds),[2][3][4] asserts that computational problems can be feasibly computed on some computational device only if they can be computed in polynomial time; that is, if they lie in the complexity class P.[5]

[...]

Alan Cobham's 1965 paper entitled "The intrinsic computational difficulty of functions"[6] is one of the earliest mentions of the concept of the complexity class P, consisting of problems decidable in polynomial time. Cobham theorized that this complexity class was a good way to describe the set of feasibly computable problems. Any problem that cannot be contained in P is not feasible, but if a real-world problem can be solved by an algorithm existing in P, generally such an algorithm will eventually be discovered.

Can you see why this could be relevant to your question?

So, the time complexity is asymptotically the same, right?

I would say so, since they seem to be equivalent in their operation. I could be wrong, though.

 

[evinda]

It introduces the P complexity class, and why polynomial time is a good way to classify "easy" problems.

I don't have access to it at this moment... So how could I explain it in a few words? (Thinking)

 

[Evgeny.Makarov]

The class P is convenient for two reasons. First, time complexity grows not too fast, so that when the problem size grows by a factor of 10 or a 100, the time generally remains feasible. See an example on the Wikipedia page about the Cobham's thesis. The second reason is that this class does not depend on the precise formulation of the computing device used (single-tape Turing machine, multi-tape machine, random-access machine, etc.). A problem that takes polynomial time with respect to one of these machines will take polynomial time with respect to any of them.

 

[evinda]

The class P is convenient for two reasons. First, time complexity grows not too fast, so that when the problem size grows by a factor of 10 or a 100, the time generally remains feasible. See an example on the Wikipedia page about the Cobham's thesis. The second reason is that this class does not depend on the precise formulation of the computing device used (single-tape Turing machine, multi-tape machine, random-access machine, etc.). A problem that takes polynomial time with respect to one of these machines will take polynomial time with respect to any of them.

I see... (Smile)
What could we say for the following proposition?

The time of a dynamic algorithm is always $O(P)$ where $P$ is the number of subproblems.

 

[Evgeny.Makarov]

The time of a dynamic algorithm is always $O(P)$ where $P$ is the number of subproblems.

Do you mean the algorithm a constant complexity? Can you give an example of a dynamic algorithm?