4
$\begingroup$

In the paper of Hsiao and Reyzin, Section $1.4$:

Note that to show that no general reduction from $P$ to $Q$ exists requires proving that $Q$ does not exist

Since the statement is about trying to rule out the implication $Q \rightarrow P$, showing that $Q$ does not exist will indeed do the opposite: it makes the implication true for the trivial reason that $(\mathsf{false} \rightarrow \mathsf{proposition})$ is $\mathsf{true}$ for any $\mathsf{proposition}$.

Could someone explain?

$\endgroup$
2
  • $\begingroup$ What makes you think "the statement is about trying to rule out the implication $Q\to P$"? $\;\;\;$ It certainly seems like it's "about trying to rule out the implication" $\: P\to Q \;$. $\;\;\;\;\;\;\;\;$ $\endgroup$
    – user991
    Jun 23, 2015 at 19:21
  • $\begingroup$ Reducing $P$ to $Q$ means existence of $Q$ implies that of $P$. $\endgroup$
    – user25240
    Jun 23, 2015 at 19:27

1 Answer 1

1
$\begingroup$

(Note that this attempted answer contains a significant amount of guessing and must not be considered reliable!)

If one assumes "there is a general reduction from $P$ to $Q$" to mean "existence of $Q$ implies existence of $P$" (which is up to interpretation since the authors do not clearly define that term, but it seems somewhat reasonable), then the statement in question is wrong: Under this assumption, it can be reformulated as

If the existence of $Q$ does not imply the existence of $P$, then $Q$ does not exist.

...whose contrapositive

If $Q$ exists, then the existence of $Q$ implies the existence of $P$.

is equivalent to "there is a reduction from $P$ to $Q$", and this is clearly untrue in general.


My best guess is, still under the assumption mentioned in the beginning, that this is a simple typo and they actually meant

Note that to show that no general reduction from $P$ to $Q$ exists requires proving that $P$ does not exist

...which is true (and still conveys the point they are trying to illustrate) since its contrapositive

If $P$ exists, then the existence of $Q$ implies the existence of $P$.

is obviously a tautology.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.