Re: Reductions in P

In article <1152988600.265406.153130@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
<ahuznot@xxxxxxxxx> wrote:
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)?

The first thing to observe is that you're now assuming some additional facts
about f and g, beyond the bare fact that they're in P. So in principle, it
is certainly possible to deduce useful information from these extra facts.

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.

That's correct.

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.
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.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
.

Relevant Pages

  • Re: linking c++ code with c library
    ... Or too many people who ignore facts which are inconvenient... ... I pointed out some cases that your algorithm would not cover. ... one posted that some obscure option of gcc would warn about this ... If you feel your original question hasn't been answered, ...
    (comp.lang.c)
  • Re: Factoring problem, my assertion revisited
    ... > Rupert wrote: ... >> solved the factoring problem. ... > rude, and unwilling to actually listen to the facts, so I presented a ... first of all could you please tell me what the algorithm ...
    (sci.math)
  • Re: Factoring problem, my assertion revisited
    ... > Rupert wrote: ... >> solved the factoring problem. ... > rude, and unwilling to actually listen to the facts, so I presented a ... first of all could you please tell me what the algorithm ...
    (sci.crypt)
  • Re: Turn a uniform number to normal random numbers
    ... FACTS ARE FACTS ... I DIDN´T say you copied me: only that your post is useless. ... Furthermore I identified the algorithm, Box- Muller’s, an useful information to the OP for ulterior self checking. ...
    (sci.stat.math)