Complexity theory’s 50-year journey to the limits of knowledge

www.quantamagazine.org

Complexity theory’s 50-year journey to the limits of knowledge

www.quantamagazine.org

bot@lemmy.smeargle.fansBM to Hacker News@lemmy.smeargle.fans · 3 years ago

Complexity Theory’s 50-Year Journey to the Limits of Knowledge | Quanta Magazine

www.quantamagazine.org

How hard is it to prove that problems are hard to solve? Meta-complexity theorists have been asking questions like this for decades. A string of recent results has started to deliver answers.

HN Discussion

You must log in or # to comment.

Chat

Hacker News@lemmy.smeargle.fans

hackernews@lemmy.smeargle.fans

You are not logged in. However you can subscribe from another Fediverse account, for example Lemmy or Mastodon. To do this, paste the following into the search field of your instance: !hackernews@lemmy.smeargle.fans

Community locked: only moderators can create posts. You can still comment on posts.

A mirror of Hacker News’ best submissions.

Visibility: Public

This community can be federated to other instances and be posted/commented in by their users.

1 user / day
1 user / week
1 user / month
1 user / 6 months
73 local subscribers
2.16K subscribers
17.5K Posts
4.31K Comments
Modlog

mods:
bot@lemmy.smeargle.fansB