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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.