7
$\begingroup$

Computational Complexity Theory is complex. My understanding of polynomial time is in relation to other time complexity classes, such as non-deterministic polynomial time. This is fine for engineers and mathematicians, but I'm looking for a simple definition of the term, suitable for laypeople.

  • Would it be incorrect to cast polynomial time as "time measured in (computational) operations?"

Obviously there would be subsequent qualifications for different time complexity classes, and time complexity may be more properly a ratio based on the problem size, but again, that's a bit more complex than what I'm looking for here.

$\endgroup$
  • 2
    $\begingroup$ Constant time: doing it once is easy doing it millions of times is easy, polynomial time: doing it once is easy doing it millions of times is hard, exponential time: doing it once is easy doing it millions of times is almost impossible. $\endgroup$ – slebetman Sep 25 '17 at 6:54
  • $\begingroup$ Are you actually trying to explain polynomial time to a lay person, or just the practical difference between a polynomial time algorithm and an exponential time algorithm? Perhaps they don't need to know what "polynomial time" actually means? $\endgroup$ – Roman Starkov Sep 25 '17 at 11:35
  • 1
    $\begingroup$ @RomanStarkov Possibly I should have made the question "Non-mathematical definition of time complexity" as opposed to specifically mentioning polynomial time (which seems to have caused some confusion about the nature of my inquiry;) Really, it's an effort to provide a very simple, very high-level definition of the underlying condition and quality of time complexity, which seems to be computational operations. A referent might be thermodynamic time, which I've seen explained it very simple terms by public scholars on science programs. $\endgroup$ – DukeZhou Sep 25 '17 at 17:09
8
$\begingroup$

"Polynomial time" is a statement about the running time of an algorithm. In theory, the running time of an algorithm is a count of the number of basic operations it does. This is expected to be proportional to the time it takes for the algorithm to run on a computer. Polynomial time means that the running time is at most some (unspecified) polynomial in the size of the input; e.g., proportional to the square of the input size, or cube, or something like that. Polynomial-time algorithms are often efficient enough to implement in practice.

See https://en.wikipedia.org/wiki/Time_complexity#Polynomial_time and https://en.wikipedia.org/wiki/Cobham%27s_thesis.

$\endgroup$
  • $\begingroup$ Thank you DW. I didn't express myself well in the question, but this is the answer I was looking for! (i.e. this answer is suitable for the general public, and requires no math.) $\endgroup$ – DukeZhou May 18 '18 at 17:04
40
$\begingroup$

Polynomial time algorithms are algorithms whose running time increases by a constant factor when the input is doubled in size.

Exponential time algorithms are algorithms whose running time increases by a constant factor when the input size increases by 1.

For laypeople you can perhaps identify NP-complete problems with problems solvable only in exponential time, although, as we know, this is wrong on many counts.

$\endgroup$
  • 1
    $\begingroup$ How is "only solvable in exponential time" any easier than the more correct "not solvable in polynomial time"? $\endgroup$ – Raphael Sep 24 '17 at 13:15
  • 1
    $\begingroup$ Since the actual belief is that these problems are solvable only in exponential time. $\endgroup$ – Yuval Filmus Sep 24 '17 at 13:36
  • 1
    $\begingroup$ For NP just say "there's a way to verify solutions, to check that they're right, in polynomial time." For NP-complete say, "these problems are interesting because you can actually build a little computer inside of the problem to verify any other problem, so every other NP problem is a special case of the NP-complete one" or so. P = NP says "if we know enough about a problem to recognize correct solutions, does that mean we in principle know enough to create them? Most experts think no..." $\endgroup$ – CR Drost Sep 24 '17 at 17:44
  • 1
    $\begingroup$ @rus9384 please reread the answer that you are replying to as you are missing some context; an $O(n^8)$ algorithm has $2^8$ as its constant. $\endgroup$ – CR Drost Sep 24 '17 at 21:16
  • 1
    $\begingroup$ Wouldn't you say the increase is bounded by a constant factor? $\endgroup$ – PyRulez Sep 25 '17 at 4:18
38
$\begingroup$

Would it be incorrect to cast polynomial time as "time measured in (computational) operations?"

Yes. Completely incorrect.

"Time" does indeed mean "time measured in (computational) operations" but you've not translated "polynomial" at all. It's like translating "twelve days" as "time measured in number of rotations of the earth on its axis." That's exactly what what "day" means, but what happened to "twelve"?

Polynomials are inherently mathematical objects and I doubt there's any way of explaining them without using mathematics. You can explain that polynomial algorithms are usually regarded as being reasonably efficient, but that's a consequence of what a polynomial relationship is, not an explanation of it.

$\endgroup$
1
$\begingroup$

There's really not much you can do to provide simple definitions of those problem spaces. Remember that problem spaces like P and NP are defined by asymptotic behavior as some number n goes to infinity. There are no layman situations where going to infinity is useful, and the precision needed to define it that way is brutal.

As such, I find its easiest to describe P and NP as "fast" and "slow," and then use the practical example of cryptography because it's interesting to people. I start with NP (because there are fast and slow P algorithms, so I want to anchor their concept of "slow" to that of exponential time before bringing in P). Everyone has dealt with some sort of geometric growth somewhere, even if its just compound interest, so there's something to start from.

Once I think they have some idea of exponential time, I introduce the cryptography link. One of the goals of cryptography is that adding 1 bit to a key doubles how long it takes someone to break it. The essential part is to connect the idea that adding work to the sender/receiver multiplies the amount of work needed by the attacker.

With that, I can then bring up Moore's law, which very roughly says computing power doubles every 18 months. That means my attacker is able to do twice as much work if he can wait for the hardware to catch up. When his attacking capability doubles, I have to add a bit. Then he doubles again, and I add a bit. Then I can show just how asymmetric this game is -- every time they do a massive amount of extra work, I have to do just a little extra work to keep things even.

Now I can teach polynomial time as algorithms that run faster than exponential time. This is a bit of a simplification, but for a layman I think it's okay. If my crypto algorithm were polynomial time, as my attacker's computational speed got better, I'd have to be adding bits quicker and quicker, bogging down the system. Everyone knows what it means when a computer runs slow!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.