[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]

Here we have denotes Polynomial Time Algorithm, and 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

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

Polynomial Time Complexity examples: , , , ...

These complexities are bounded by polynomials on the form

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: , , ...

-- where is a constant,

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

Also notice that the question: 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

This post has been edited by khaled: 12 February 2012 - 08:01 PM

[Schrödinger's hat]

Hyperreal_Logic, on 12 February 2012 - 07:46 AM, said:

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 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 where c is a constant operations to solve the problem.

This is good, because polynomials grow slowly compared to exponentials (stuff like ) 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

khaled, on 12 February 2012 - 07:53 PM, said:

Here we have denotes Polynomial Time Algorithm, and 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
A Non-Polynomial Time Algorithm is an algorithm with a Time Complexity that progress fast,
Polynomial Time Complexity examples: , , , ...
These complexities are bounded by polynomials on the form
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: , , ...
-- where is a constant,
Note: the above definitions are unofficial, they are to help understand.
Also notice that the question: 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.

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 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 or not

[khaled]

Schrödinger, on 12 February 2012 - 11:42 PM, said:

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 ...

Schrödinger, on 12 February 2012 - 11:42 PM, said:

This includes problems in 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 or not

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]

khaled, on 13 February 2012 - 04:12 PM, said:

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 non-polynomial would exclude NP.

Quote

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.

Quote

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]

khaled, on 13 February 2012 - 04:12 PM, said:

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]

Schrödinger, on 14 February 2012 - 08:26 AM, said:

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 non-polynomial would exclude NP.

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

Schrödinger, on 14 February 2012 - 08:26 AM, said:

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

Schrödinger, on 14 February 2012 - 08:26 AM, said:

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)

D H, on 14 February 2012 - 02:07 PM, said:

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]

Quote

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]

khaled, on 14 February 2012 - 11:20 PM, said:

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]

immortal, on 29 February 2012 - 10:07 AM, said:

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 ...

phillip1882, on 29 February 2012 - 03:08 AM, said:

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

denote algorithms that are polynomial-time bounded, in other words:

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

This post has been edited by khaled: 29 February 2012 - 11:43 PM