When studying mathematics, one often finds something like:

'The following statements are equivalent:

$1$. Statement $1$

$2$. Statement $2$


$n$. Statement $n$'

I'm looking for some examples where the implications $1\implies 2 \implies \ldots\implies n\implies 1$ are trivial or very easy but the converse implications are very hard without going through another statement, i.e. each arrow in $n\implies n-1\implies\ldots\implies 1\implies n$ is hard to prove directly.

  • 1
    $\begingroup$ A lot of times, these statements can get hard when $n-1$ and $n$ are related where $n-1$ appears stricter than $n$. In other words, $n-1$ says that there exists something with $5$ conditions and $n$ only uses $3$ of the conditions. $\endgroup$ – Michael Burr Apr 21 '17 at 0:35
  • $\begingroup$ This probably isn't what you had in mind, but depending on what you are looking for, may be helpful. In the definition of a trapdoor function, for example factoring large numbers in RSA, it would be hard to go backwards for a particular set of parameters. You may have knowledge in the earlier statement (like the values of primes $p$ and $q$) that you don't in later statements. You'd have to craft the earlier statements with the actual values of the various parameters. $\endgroup$ – Χpẘ Apr 21 '17 at 1:33

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.