I am reading a paper and it uses the expression "polynomial delay" which I don't understand. It is used in conjonction with the big O notation, which I'm familiar with.

Here is a example sentence showing how it is used:

The loop is executed in time $O(n^2(e+n))$, which makes a polynomial delay for the output of the data.

I've tried searching a bit but I can only seem to find other papers and no definition.

  • $\begingroup$ Do you have a link to the paper in question? My guess would be that it is trying to simply state that you have to wait a polynomial amount of time for the answer (algorithm to conclude). $\endgroup$
    – mdxn
    Sep 26 '13 at 2:15
  • $\begingroup$ So it would be a kind of synonym for polynomial complexity? Here is the paper : sciencedirect.com/science/article/pii/S0166218X00003395# $\endgroup$ Sep 26 '13 at 2:40
  • $\begingroup$ Please include the reference (with author, title, year) in your question. $\endgroup$
    – Raphael
    Sep 14 '16 at 8:10

The term "polynomial delay", in this case, appears to refer to the time complexity of generating (or enumerating) subsequent solutions. This is a bit different than our standard notion of runtime, since we usually only consider single executions of a machine or algorithm on an input. The delay complexity measure deals with time spent between enumerations through a set (e.g. a set of solutions).

Suppose you are working with a large dataset or database. You might want to step through or enumerate solutions to some problem using that data as an input. There are at least two steps involved here:

  1. Initialization (perhaps generating your first solution)
  2. Computing the next solution for the purpose of enumeration.

For example, you might use a polynomial space or exponential time algorithm to initialize and preprocess your data. To find or generate multiple solutions to a problem, you may only need to do a little bit of extra work. The time complexity with generating that next solution is the time delay complexity measure that you encountered in that paper. In particular, the time delay between enumerations is polynomial in respect to the input.

Jan Ramon mentions this and other time complexity measures in his talk on "General Graph Refinement with Polynomial Delay": http://videolectures.net/mlg07_ramon_ggr/


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.