1
$\begingroup$

I am currently studying about polynomial time in Comp Theory. The definition for polynomial time given in my textbook as follows: $$P= \bigcup_{k}TIME(n^k)$$ I have not seen the Union over k notation before. K is a constant. A quick introduction to the meaning of this notation would be enormously helpful.

Thank you

|cite|improve this question
$\endgroup$
  • $\begingroup$ Simple: $k$ is not a constant here. It's a bound variable. $\endgroup$ – Raphael♦ Apr 10 '16 at 12:28
  • $\begingroup$ This is a good question! That notation is indeed confusing, especially if this is the first time you see it. As the other comments/answers say, it is a shorthand for $\cup_{k=1}^\infty$. $\endgroup$ – Ran G. Apr 11 '16 at 0:55
3
$\begingroup$

Authors often leave out the domain of the union if it is clear within the context. Here, $k$ is a natural number, i.e. $P = \bigcup\limits_{k \in \mathbb{N}} TIME(n^k) $. This is what it means for a complexity function to be bounded by a polynomial: there is a constant $k$ such that the function is in $\mathcal{O}(n^k)$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ (Also, the result will be the same in this case if k ranges over the integers, or the rationals, or the reals, or the positive rationals, or the positive reals. ​ (or, for that matter, the primes, etc.)) ​ ​ ​ ​ $\endgroup$ – user12859 Apr 9 '16 at 22:49
  • $\begingroup$ So its the domain of the union. Got it. Thank you. $\endgroup$ – Delete My Account Apr 10 '16 at 6:38
  • $\begingroup$ @PenguinsAndApples No, not the domain; that's $\mathbb{N}$. It's a bound variable. $\endgroup$ – Raphael♦ Apr 10 '16 at 12:28

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.