johncarlosbaez, (edited )
@johncarlosbaez@mathstodon.xyz avatar

The precise location of the boundary between the knowable and the unknowable is itself unknowable. But we 𝑑𝑜 know some details about 𝑤ℎ𝑦 this is true, at least within mathematics. It's being studied rigorously in a branch of theoretical computer science called 'meta-complexity theory'.

For some reason it's hard to show that math problems are hard. In meta-complexity theory, people try to understand why.

For example, most of us believe P ≠ NP: merely being able to 𝑐ℎ𝑒𝑐𝑘 the answer to a problem efficiently doesn't imply you can 𝑠𝑜𝑙𝑣𝑒 it efficiently. It seems obvious. But despite a vast amount of work, nobody has been able to prove it!

And in one of the founding results of meta-complexity theory, Razborov and Rudich showed that if a certain attractive class of strategies for proving P ≠ NP worked, then it would be possible to efficiently crack all codes! None of us think 𝑡ℎ𝑎𝑡'𝑠 possible. So their result shows there's a barrier to knowing P ≠ NP.

I'm simplifying a lot of stuff here. But this is the basic idea: they proved that it's probably hard to prove that a bunch of seemingly hard problems are really hard.

But note the 'probably' here! Nobody has 𝑝𝑟𝑜𝑣𝑒𝑑 we can't efficiently crack all codes. And this too, seems very hard to prove.

So the boundary between the knowable and unknowable is itself shrouded in unknowability. But amazingly, we can prove theorems about it!

https://www.quantamagazine.org/complexity-theorys-50-year-journey-to-the-limits-of-knowledge-20230817/

  • All
  • Subscribed
  • Moderated
  • Favorites
  • random
  • ngwrru68w68
  • rosin
  • GTA5RPClips
  • osvaldo12
  • love
  • Youngstown
  • slotface
  • khanakhh
  • everett
  • kavyap
  • mdbf
  • DreamBathrooms
  • thenastyranch
  • magazineikmin
  • megavids
  • InstantRegret
  • normalnudes
  • tacticalgear
  • cubers
  • ethstaker
  • modclub
  • cisconetworking
  • Durango
  • anitta
  • Leos
  • tester
  • provamag3
  • JUstTest
  • All magazines