English subtitles

← 07-14 One More Detail Solution

Get Embed Code
1 Language

Showing Revision 1 created 10/03/2012 by Amara Bot.

  1. And the answer here is that we need to say something about
  2. the length of the formula, because as you know,
  3. we are measuring running time as a function of the size of the input.
  4. Now if you have N variables,
  5. I think it's very convenient to measure the running time as a function of N,
  6. but we can only do that if we know that
  7. the length of the formula is also some function of N
  8. or if the length of the formula is polynomial in N to be more precise.
  9. So just to be very precise, from now on
  10. we will always assume that the total length
  11. of this Boolean formula that we are given
  12. is polynomial in N,
  13. the number of variables.