Timeline for Proof complexity of two directions of equivalency?
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 18, 2014 at 22:18 | comment | added | Joel David Hamkins | Oh, I also expect that there are interesting non-trivial examples. I had just wanted to point out that the phenomenon is much more common than one might have expected, since it also includes all these trivial instances. | |
| May 18, 2014 at 16:39 | comment | added | Ian Agol | Ok, I thought there might be a more non-trivial example, which didn't just follow from the existence of arbitrarily long proofs. | |
| May 18, 2014 at 16:38 | vote | accept | Ian Agol | ||
| May 17, 2014 at 20:29 | comment | added | Joel David Hamkins | Another class of trivial examples: take any provable statement $p$ having no short proof, and consider the equivalence $\top\leftrightarrow p$. Proving the forward implication is just as hard as proving $p$, while the converse implication is immediate. | |
| May 17, 2014 at 19:56 | history | edited | Joel David Hamkins | CC BY-SA 3.0 |
deleted 4 characters in body
|
| May 17, 2014 at 19:50 | history | answered | Joel David Hamkins | CC BY-SA 3.0 |