Re: Reductions in P

tchow@xxxxxxxxxxxxx wrote:

You correctly see that there isn't much point in polytime reductions
between problems 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)).

Does this argument hold water?

.

Relevant Pages

  • Re: Any way to take a word as input from stdin ?
    ... snip ... ... If he wants to use a C++ algorithm as illustration he ... His question was basically about how to translate the C++ algorithm to ... So what you're saying is that he must answer his own question ...
    (comp.lang.c)
  • Re: Any way to take a word as input from stdin ?
    ... snip ... ... If he wants to use a C++ algorithm as illustration he ... His question was basically about how to translate the C++ algorithm to ... So what you're saying is that he must answer his own question ...
    (comp.lang.c)
  • Re: Help with algorithm of Sieve of Eratosthenes
    ... translate this algorithm to Visual Basic, ... Dim topNumber As Integer = 1000000 ... Dim numbers As BitArray = New BitArray ...
    (microsoft.public.dotnet.languages.vb)
  • Re: Help with algorithm of Sieve of Eratosthenes
    ... translate this algorithm to Visual Basic, ... Dim topNumber As Integer = 1000000 ... Dim numbers As BitArray = New BitArray ...
    (microsoft.public.dotnet.languages.vb)
  • Re: translating imperative pseudocode to functional
    ... In general graph algorithms aren't easy ... to translate into a purely functional language. ... A quick look at the contents showed me that it implements an algorithm ... > i have the following pseudocode algorithm for finding the largest set ...
    (comp.lang.functional)