Conversation

Jan 26, 2021

alright just for fun: AMA but only about math, will attempt to speed-explain stuff with as few symbols and equations as possible and see what happens (esp happy to field questions about stuff that seems basic to you and that you feel like you should've gotten a long time ago!)

snav

@qorprate

Jan 26, 2021

i was wondering about (algorithmic) complexity theory and P?=NP and i was curious whether you know of some category theory-like field that attempts to ground complexity theory axiomatically in a way that nudges us toward a better understanding of how P/NP actually relate

QC (in Berlin 7/29-??? w/ COVID

)

@QiaochuYuan

Replying to

@qorprate

sadly i do not. there's this thing i wish i had a better handle on where "hard analysis" - like real down-to-earth numerical estimates of things - seems to be the "opposite" of category theory, and complexity theory is enough like that that it feels un-categorical

8:12 PM · Jan 26, 2021Twitter Web App

Replying to

yeah -- i should try and find something that tries to really formalize the assumptions of category theory, because the "reduction" method seems potentially flawed (definitely flawed in practice, where literally all runtimes are "constant" if you squint hard at a computer)