Read on Twitter
Among the many mind-blowing things in complexity|theory are the "win-win" theorems. If one can show that "if A doesn& #39;t work, well then B must"... we& #39;re done.
E.g., "A is efficient if [Hard Conjecture] is true, but B is efficient if it isn& #39;t." No need to prove [Hard Conjecture]!
E.g., "A is efficient if [Hard Conjecture] is true, but B is efficient if it isn& #39;t." No need to prove [Hard Conjecture]!
It& #39;s even more elegant as the "wins" are the same. Sometimes, you get
- if [X] holds, then [something I want]
- if [X] doesn& #39;t, then [something else I want]
but there are many examples where the conclusion is identical in both cases! Just taking a different path to get there...
- if [X] holds, then [something I want]
- if [X] doesn& #39;t, then [something else I want]
but there are many examples where the conclusion is identical in both cases! Just taking a different path to get there...
Incidentally, if you are interested in that sort of arguments in complexity and learning theory, then definitely check out Igor Carboni Oliveira& #39;s work ( https://www.dcs.warwick.ac.uk/~igorcarb/ ).">https://www.dcs.warwick.ac.uk/~igorcarb...
