A reducibility on pairs of problems in U that
preserves tractability, i.e., a reducibility
such that the following two properties hold:
- If P reduces to Q and Q is in
T then P is in T.
- If P reduces to Q and Q
reduces to R them P reduces to
R.
Any such reducibility by definition (in particular, by
the first property above) also has the following
third property:
- If P reduces to Q and P is
not in T (modulo conjecture X) then
Q is not in T (modulo conjecture X).