[Cs4800] Quick question about polynomial time

[Karl Lieberherr]

Hi Andrei and Ken:

even O(n^2 * (2^{|M|}) would qualify as polynomial time, provided |M| is a
constant.
In our case, |M| is 2 or 3.

Therefore, O(n^2) * (2^{|M|}) = O(n^2 * C) = O(n^2) which is polynomial.

The term that is used in this context is: fixed parameter tractability.

To learn more about this, read the first two definitions in:
http://www.ccs.neu.edu/home/lieber/courses/algorithms/cs4800/f10/resources/fixedParamNP.pdf

-- Karl

On Mon, Oct 11, 2010 at 7:32 PM, Kenneth K Sham <sham.k at husky.neu.edu>wrote:

> Andrei,
> You are right. n^2 is polynomial and not exponential. Exponential would be
> something like 2^n. Exponential time algorithms grow much faster than
> polynomial. For example:
>
> 500^3  is far less than  3^500.  I'm pretty sure it's even far less than
> 2^500.
>
> Ken
>
>
>
> On Mon, Oct 11, 2010 at 5:47 PM, Andrei Mackenzie <andrei at ccs.neu.edu>wrote:
>
>> Hi all,
>>
>> Assuming we let m = |M| and n = # of directed trees whose GCP we are
>> interested in, would an algorithm that is bounded by O(n^2 * m) be
>> considered polynomial? I don't think it's exponential, since neither n nor m
>> appear as an exponent, but I'm not sure if it's still polynomial.
>>
>> Thanks in advance!
>>
>> --
>> Andrei Mackenzie
>>
>> _______________________________________________
>> Cs4800 mailing list
>> Cs4800 at lists.ccs.neu.edu
>> https://lists.ccs.neu.edu/bin/listinfo/cs4800
>>
>
>
> _______________________________________________
> Cs4800 mailing list
> Cs4800 at lists.ccs.neu.edu
> https://lists.ccs.neu.edu/bin/listinfo/cs4800
>
>
-------------- next part --------------
HTML attachment scrubbed and removed