Re: Reductions in P

What about this hypothetical scenario: I have P1, P2, P3 in P, and P1
is reducible to P2 via f(), and P2 is reducible to P3 via g().
Something like:

P1 <= _f P2 <=_g P3 f in O(n log n), g in O(^2)

Let's say that I know an O(n^4) algorithm A3 to solve P3. Can I
construct an algorithm for P2 (and P1) using A3 and g (and f)?
My first guess is yes, because I can take an instance p2 of P2, translate
it to an instance p3 of P3 via g(), so effectively I have the following
algorithm

A3(g(p2))

... to solve p2 in P2.

Moreover, I know that it's complexity is
MAX(complexity(A3), complexity(g)) = MAX(O(n^4), O(n^2)).

Not quite. Given what you've said so far, it is possible that g might
take an input of size m and generate an output of size as big as m^2.

I see, because g is O(n^2). Actually, IMHO it would be more precise to
say that output of g() is O(m^2), and not "as big as m^2". (Because the
constant in O for g could be very small, for example.)


This output will become the input for A3, which runs in time proportional
to the 4th power of the size m^2 of *its* input. Since (m^2)^4 = m^8,
the compound algorithm may take as long as the 8th power of the size m
of the original input.

So if output of g() is O(m^2), and A3(g(p2)) is an algorithm for P2,
then the complexity of A3(g()) is O((O(m^2))^4) = O(O(m^8)) = O(m^8).

.

Relevant Pages

  • Re: Another way to do x^n
    ... \ raise float to positive integer power ... DUP 0= IF DROP FDROP 1e0 EXIT THEN ... FDUP F0= IF DROP FDROP 0e0 EXIT THEN ... Recursion unnecessarily obfuscates the algorithm. ...
    (comp.lang.forth)
  • Re: Another way to do x^n
    ... \ raise float to positive integer power ... FDUP F0= IF DROP FDROP 0e0 EXIT THEN ... Recursion unnecessarily obfuscates the algorithm. ...
    (comp.lang.forth)
  • Re: to Matt,
    ... algorithm that can run BWT in linear time (with respect to the input ... Quantum computers are thing of past, ... I can use Jules' random compression ... drill a power cord from WB's super nuclear power plant to Sachin's ...
    (comp.compression)
  • Re: Powers of 5
    ... This should give you the modified algorithm almost immediately. ... Courses with greater emphasis on programming have entered ... require the argument to be a power of 2. ...
    (sci.math)
  • Re: to Matt,
    ... algorithm that can run BWT in linear time (with respect to the input ... Quantum computers are thing of past, ... I can use Jules' random compression ... drill a power cord from WB's super nuclear power plant to Sachin's ...
    (comp.compression)