[Inquiry] Reductions Among Relations

[Jon Awbrey]

o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o

RAR.  Note 1

o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o

One of the things that keeps the general problem of "reductions among relations" (RAR)
from being fully well-defined is that you would have to survey all of the conceivable
ways of "getting new relations from old" in order to say precisely what is meant by
the claim that "the relation L is reducible to the set of relations {L_j : j in J}".
In other words, this is tantamount to claiming that if you had a set of "simpler"
relations L_j, for indices j in some set J, that this collection of data would
somehow or other fix the original relation L that you were seeking to analyze,
to determine, to specify, or to synthesize.

In my experience, however, most people will eventually settle on
either one of two different notions of reducibility as capturing
what they have in mind, namely:

1.  Reduction Under Composition.
2.  Reduction Under Projections.

As it happens, there is an interesting relationship between these
two notions of reducibility, the implications of which I am still
in the middle of studying, so I will try to treat them in tandem.

Jon Awbrey

o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o~~~~~~~~~o