Polynomial Time - What does it mean to be bounded by a polynomial?

[Hyperreal_Logic]

I am trying to conceptualize the notion of polynomial time. Can someone please tell me, in not-so-formal terms, what it means for something to be bounded by a polynomial?

 

Any help will be much appreciated.

[khaled]

[math]P \neq NP[/math]

 

Here we have [math]P[/math] denotes Polynomial Time Algorithm, and [math]NP[/math] denotes Non-Polynomial Time Algorithm,

 

-- The statement above is interpreted "there exist no polynomial time algorithm to solve a non-polynomail problem"

 

A Polynomial Time Algorithm is an algorithm with a Time Complexity that progress slow according to a huge input size [math]N[/math]

 

A Non-Polynomial Time Algorithm is an algorithm with a Time Complexity that progress fast,

 

Polynomial Time Complexity examples: [math]O© \;[/math], [math]\; O(log N) \;[/math], [math] \; O(N^c) \;[/math], [math] \; O(\sqrt{N}) \;[/math] ...

 

These complexities are bounded by polynomials on the form [math]O(\sum_{i=0}^{k}{c_i N^i})[/math]

 

So basically any complexity that is not bounded by (progress faster than) polynomials as mentioned above, is a Non-Polynomial,

 

:: It's like saying "anyone that runs slower than Tom is in group Tom, others are in group Non-Tom" .. so "Tom is a bound for members of group Tom".

 

Non-Polynomial Time Complexity examples: [math] \; c^N \;[/math], [math] \; N^N \;[/math], [math] \; N ! \;[/math] ...

 

-- where [math]c[/math] is a constant,

 

Note: the above definitions are unofficial, they are to help understand.

 

Also notice that the question: [math]is \;\; P \; = \; NP[/math] is still an open problem in Computer Science and Mathematical Logic,

which ask if there exist a polynomial time algorithm that can solve an NP problem

Edited February 12, 2012 by khaled

[Schrödinger's hat]

I am trying to conceptualize the notion of polynomial time. Can someone please tell me, in not-so-formal terms, what it means for something to be bounded by a polynomial?

 

Any help will be much appreciated.

 

The idea is that you have a number [math]N[/math] which measures the size of your problem.

This could be the number of digits in a number, or the number of elements in an array you want to sort.

 

If something is polynomial time, it means that it takes no more than [math]N^c[/math] where c is a constant operations to solve the problem.

 

This is good, because polynomials grow slowly compared to exponentials (stuff like [math]c^N[/math]) or similar.

 

So as N gets very large, the number of operations required is still managable for a polynomial time algorithm (although as c gets bigger, this is less and less true).

 

A good example is factoring. There is no known (classical -- ask if you're really curious) factoring algorithm which is polynomial in the number of digits.

As a result adding a digit (approximately) doubles the amount of work required.

Checking the factors, however, consists of a multiplication which is polynomial. You'd have to (again, very approximately) double the number digits to double the amount of work required.

 

Which brings me to [math]P \mbox{ vs. } NP[/math]

[math]P \neq NP[/math]

Here we have [math]P[/math] denotes Polynomial Time Algorithm, and [math]NP[/math] denotes Non-Polynomial Time Algorithm,

-- The statement above is interpreted "there exist no polynomial time algorithm to solve a non-polynomail problem"

A Polynomial Time Algorithm is an algorithm with a Time Complexity that progress slow according to a huge input size [math]N[/math]

A Non-Polynomial Time Algorithm is an algorithm with a Time Complexity that progress fast,

Polynomial Time Complexity examples: [math]O© \;[/math], [math]\; O(log N) \;[/math], [math] \; O(N^c) \;[/math], [math] \; O(\sqrt{N}) \;[/math] ...

These complexities are bounded by polynomials on the form [math]O(\sum_{i=0}^{k}{c_i N^i})[/math]

So basically any complexity that is not bounded by (progress faster than) polynomials as mentioned above, is a Non-Polynomial,

:: It's like saying "anyone that runs slower than Tom is in group Tom, others are in group Non-Tom" .. so "Tom is a bound for members of group Tom".

Non-Polynomial Time Complexity examples: [math] \; c^N \;[/math], [math] \; N^N \;[/math], [math] \; N ! \;[/math] ...

-- where [math]c[/math] is a constant,

Note: the above definitions are unofficial, they are to help understand.

Also notice that the question: [math]is \;\; P \; = \; NP[/math] is still an open problem in Computer Science and Mathematical Logic,

which ask if there exist a polynomial time algorithm that can solve an NP problem

 

Khaled, please check your facts before posting.

 

[math]NP[/math] Stands for non-deterministic polynomial.

This is a set of problems (factoring is one) where the answer can be checked in polynomial time.

 

This includes problems in [math]P[/math] where the answer can be calculated (not just checked) in polynomial time as well as problems that have no known solution in polynomial time (but can still be checked that quickly).

(ie. all problems in P are in NP, but it is not known if all problems in NP are in P

 

As Khaled said, it is not known if these problems (the ones that can be checked but not solved quickly) have a fast solution that is undiscovered [math]P=NP[/math] or not [math]P\neq NP[/math]

[khaled]

[math]NP[/math] Stands for non-deterministic polynomial.

This is a set of problems (factoring is one) where the answer can be checked in polynomial time.

 

Your note is right, but my definition is not wrong, we use the term "non-polynomial" as a short term in computer science ...

 

This includes problems in [math]P[/math] where the answer can be calculated (not just checked) in polynomial time as well as problems that have no known solution in polynomial time (but can still be checked that quickly).

(ie. all problems in P are in NP, but it is not known if all problems in NP are in P

 

As Khaled said, it is not known if these problems (the ones that can be checked but not solved quickly) have a fast solution that is undiscovered [math]P=NP[/math] or not [math]P\neq NP[/math]

 

we use the terms "solve" and "verify\decide" instead of "calculate" and "check", it's an algorithm not an evaluation

 

Problems can be either solved or verified .. the optimal solution to a problem tell us if it's P, or NP

.. verification of a problem is a decision problem that returns TRUE if there exist a solution, FALSE otherwise

 

------------------

 

Note that Problems are solvable or unsolvable .. Solvable Problems are either decidable or undecidable

.. the complexity for verification of a problem is always less than or equal the complexity of solving

[Schrödinger's hat]

Your note is right, but my definition is not wrong, we use the term "non-polynomial" as a short term in computer science ...

No, non-polynomial means non-polynomial. Quite distinct from non-deterministic polynomial (something that would be polynomial given a non-deterministic turing machine). If it turns out that [math]P=NP[/math] non-polynomial would exclude NP.

 

we use the terms "solve" and "verify\decide" instead of "calculate" and "check", it's an algorithm not an evaluation

Pointing out that I didn't use the exact same jargon as someone else is barely relevant.

 

Problems can be either solved or verified .. the optimal solution to a problem tell us if it's P, or NP

.. verification of a problem is a decision problem that returns TRUE if there exist a solution, FALSE otherwise

Wrong again. Verification will return true if the given input is a solution to the problem. If verification were possible without a test input, then primality testing would be trivial.

[D H]

Your note is right, but my definition is not wrong, we use the term "non-polynomial" as a short term in computer science ...

I side with Schrödinger's hat here. NP means non-deterministic polynomial. By saying "non-polynomial" instead of "non-deterministic polynomial" you are implicitly assume P≠NP. We don't know that yet. That's the whole point of the P versus NP conundrum.

 

There are algorithms that are known not to be polynomial in space or time, even with the aid of an oracle. These fall in a different set of classes than the NP algorithms. Computer scientists who study complexity theory do not use NP to describe these algorithms that are known not to be polynomial in nature. They instead use terms like EXPTIME or EXPSPACE instead.

[khaled]

No, non-polynomial means non-polynomial. Quite distinct from non-deterministic polynomial (something that would be polynomial given a non-deterministic turing machine). If it turns out that [math]P=NP[/math] non-polynomial would exclude NP.

 

You are right, and again .. we use it as a short form

 

Pointing out that I didn't use the exact same jargon as someone else is barely relevant.

 

I thought you know better than me, it's not about jargons .. solve and calculate have different meanings, verify is not check

 

Wrong again. Verification will return true if the given input is a solution to the problem. If verification were possible without a test input, then primality testing would be trivial.

 

Can you revise your informations, checking an answer can be a problem itself you know, it's not using a calculator to check the result of an equation.

 

The input is the problem, the verification algorithm check if there exist at least 1 solution for the given problem. there is a difference between asking

 

"are there blue balls in the box ?" (verification), "is this a blue ball ?" (checking), and "bring me a blue ball from the box." (solving)

 

I side with Schrödinger's hat here. NP means non-deterministic polynomial. By saying "non-polynomial" instead of "non-deterministic polynomial" you are implicitly assume P≠NP. We don't know that yet. That's the whole point of the P versus NP conundrum.

 

There are algorithms that are known not to be polynomial in space or time, even with the aid of an oracle. These fall in a different set of classes than the NP algorithms. Computer scientists who study complexity theory do not use NP to describe these algorithms that are known not to be polynomial in nature. They instead use terms like EXPTIME or EXPSPACE instead.

 

1. P=NP is an open problem, currently, computer scientists assume that P≠NP since no one have ever came up with a P algorithm to solve an NP problem,

so it's not because I said "non-polynomail" instead of "non-deterministic polynomial", that was a short form we use

 

2. computer scientists use P and NP in general, technically we use the Big O notation, the classes are literature

 

3. when I say "verification is a decision problem in which we return TRUE if there exist at least 1 solution for the given problem", don't assume we

make things happens in a flash, the verification itself is a problem too

[phillip1882]

I am trying to conceptualize the notion of polynomial time. Can someone please tell me, in not-so-formal terms, what it means for something to be bounded by a polynomial?

 

Any help will be much appreciated.

a polynomial is an equation of the form n^a +n^(a-1) +n^(a-2)... n^3 +n^2 +n +1 where n is the size of the input.

to say a problem is bounded by a polynomial, generally means it's an "easy" problem.

the most common example i can think of would be sorting.

say you have a list of values of unknown magnitude (they can be as big or as small as desired) and you want to place them from smallest (closest to -infinity) to largest (closest to +infinity) there are many approaches to solving this problem, at worst it takes n^2 time, where n is the number of values, and at best it takes n*log(n). both are considered polynomial times.

to say a problem is non-polynomial, generally means it's a "hard" problem.

the classic non-polynomial time algorithm is the traveling salesman problem.

imagine you have a bunch of cities each with one or more connecting roads. is it possible to visit every city only once, without going back over the same road?

this sounds easy to solve, but is actually quite hard. with enough cities and enough roads, it could literally be "impossible" (take a very long time to determine).

the good news is, with most problems that are non-polynomial, once you have an answer, generally its fairly "easy" (polynomial time) to check if you're right.

[immortal]

3. when I say "verification is a decision problem in which we return TRUE if there exist at least 1 solution for the given problem", don't assume we

make things happens in a flash, the verification itself is a problem too

 

Both P and NP problems are decidable problems which means that there exist algorithms which can check whether the given inputs satisfy the constraints or not. There is a lot of difference between checking whether a number is an armstrong number or not and generating a series of armstrong numbers say from 1 to 1000.

 

Halting problem is classified as an undecidable problem for which there is no algorithm to check whether a given input and a program halts or runs forever.

[khaled]

Both P and NP problems are decidable problems which means that there exist algorithms which can check whether the given inputs satisfy the constraints or not. There is a lot of difference between checking whether a number is an armstrong number or not and generating a series of armstrong numbers say from 1 to 1000.

 

Halting problem is classified as an undecidable problem for which there is no algorithm to check whether a given input and a program halts or runs forever.

 

It's a huge confusion actually,

 

Verification: check if there exist at least 1 solution for the given problem.

 

Check: check if the input is a valid solution for the given problem.

 

It's just like the difference between "are there BLUE balls in the box ?" and "is this a BLUE ball ?", where the given

problem is "get a BLUE ball from the box".

 

Decidability: A language is called decidable if there exists a method - any method at all - to determine

whether a given word belongs to that language or not. --Wikipedia

 

Actually decidability is not a simple concept, I know the concept but I don't understand it that I don't have enough understanding,

Halting problem is undecidable, but it is partial-decidable.

 

In Algorithms, decidability can be simple as deciding weather the input is a solution to the given problem, just like the example

you gave of armstrong numbers, or can be complex as deciding weather an input is a member of the set of solutions for the given

problem, which can be described in a different way to Turing Machine, saying is the state that this solution ends with exist in the set

of final states F ...

 

a polynomial is an equation of the form n^a +n^(a-1) +n^(a-2)... n^3 +n^2 +n +1 where n is the size of the input.

to say a problem is bounded by a polynomial, generally means it's an "easy" problem.

the most common example i can think of would be sorting.

say you have a list of values of unknown magnitude (they can be as big or as small as desired) and you want to place them from smallest (closest to -infinity) to largest (closest to +infinity) there are many approaches to solving this problem, at worst it takes n^2 time, where n is the number of values, and at best it takes n*log(n). both are considered polynomial times.

to say a problem is non-polynomial, generally means it's a "hard" problem.

the classic non-polynomial time algorithm is the traveling salesman problem.

imagine you have a bunch of cities each with one or more connecting roads. is it possible to visit every city only once, without going back over the same road?

this sounds easy to solve, but is actually quite hard. with enough cities and enough roads, it could literally be "impossible" (take a very long time to determine).

the good news is, with most problems that are non-polynomial, once you have an answer, generally its fairly "easy" (polynomial time) to check if you're right.

 

It's not about how much time we need to solve a problem with 10 cities for example, it's the question of how the algorithm progress with input increase

 

[math]P[/math] denote algorithms that are polynomial-time bounded, in other words: [math]O(Time(\alpha)) \leq O(n^c) \;\;\rightarrow\;\; \alpha \;is\;P[/math]

 

where c is a constant, n is the size of input.

Edited February 29, 2012 by khaled