You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.
Jules Hedges (Feb 20 2021 at 14:18):Funny thing, back when we created this one, I had in mind that if it was a success (which it was), I would create a much bigger Zulip instance for Theory B, the half of theoretical computer science that includes logic, semantics, programming languages etc. And then I just... didn't
Peter Arndt (Feb 20 2021 at 16:48):What is the other half of theoretical computer science?
Fawzi Hreiki (Feb 20 2021 at 16:55):I’m guessing complexity theory etc..
Jules Hedges (Feb 20 2021 at 16:58):Yeah, broadly "algorithms"
James Wood (Feb 20 2021 at 17:01):https://cstheory.stackexchange.com/questions/1521/origins-and-applications-of-theory-a-vs-theory-b
John Baez (Feb 20 2021 at 17:33):That other half is the BIG half.
John Baez (Feb 20 2021 at 17:34):For that other half I think there's a vast array of discussion forums.
John Baez (Feb 20 2021 at 17:34):(I don't know much about 'em, though.)
Fawzi Hreiki (Feb 20 2021 at 17:44):Also less in touch with categorical methods - although Noson Yanofsky is making some inroads.
John Baez (Feb 20 2021 at 17:59):True. Saying they're less in touch with categorical methods is sort of like the British saying "the continent is cut off" by fog in the English channel. :upside_down:
John Baez (Feb 20 2021 at 18:00):They'd probably say category theory is out of touch with the really important problems of computer science.
Morgan Rogers (he/him) (Feb 20 2021 at 18:02):If no one has solved P vs NP in 5 years or so, I'll devote a chunk of my life to using category theory to resolve it, just to show them the error of their ways.
John Baez (Feb 20 2021 at 18:03):That'll show 'em. And you should announce this now. "If you folks still haven't solved P vs NP in five years, I will have to solve it using category theory". :upside_down:
Jules Hedges (Feb 20 2021 at 18:05):Of course there's a lot of deep connections between the two sides. You can't just split a subject in half an expect them to forget about each other
Morgan Rogers (he/him) (Feb 20 2021 at 18:14):John Baez said:
That'll show 'em. And you should announce this now. "If you folks still haven't solved P vs NP in five years, I will have to solve it using category theory". :upside_down:
Alright, challenge accepted, although I'll round up a bit.
If P vs NP hasn't been resolved by the end of 2026, I will (attempt to) resolve it using category theory in 2027.
Jules Hedges (Feb 20 2021 at 18:16):This is where I mention geometric complexity theory
Jules Hedges (Feb 20 2021 at 18:16):"The idea behind the approach is to adopt and develop advanced tools in algebraic geometry and representation theory (i.e., geometric invariant theory) to prove lower bounds for problems. Currently the main focus of the program is on algebraic complexity classes. Proving that computing the permanent cannot be efficiently reduced to computing determinants is considered to be a major milestone for the program. These computational problems can be characterized by their symmetries. The program aims at utilizing these symmetries for proving lower bounds. "
-- https://en.wikipedia.org/wiki/Geometric_complexity_theory
Jules Hedges (Feb 20 2021 at 18:17):"The approach is considered by some to be the only viable currently active program to separate P from NP. However, Ketan Mulmuley believes the program, if viable, is likely to take about 100 years before it can settle the P vs. NP problem."
Morgan Rogers (he/him) (Feb 20 2021 at 18:20):Okay, I'll have plenty of time to submit my attempt then lol
Fawzi Hreiki (Feb 20 2021 at 18:28):Stuart Kurtz, a prominent complexity theorist, said in a poll of academics on the question: "Knowing Ketan Mulmuley, I live in fear that the solution will be via algebraic geometry, and it will come soon enough that I’ll be expected to understand it. An alternative nightmare is that the undergraduate who solves it will publish his solution in French."
Fawzi Hreiki (Feb 20 2021 at 18:29):The poll.
Jules Hedges (Feb 20 2021 at 18:31):The other possibility is the xkcd one, "Some engineer out there has solved P vs NP and it's locked up in an electric eggbeater calibration routine". The alt-text of https://xkcd.com/664/
Jules Hedges (Feb 20 2021 at 18:33):Fawzi Hreiki said:
The poll.
The mention of higher homology on page 3 is interesting...
Jules Hedges (Feb 20 2021 at 18:34):I read a paper along those lines, describing some complexity with homology (or maybe cohomology, I don't remember)
John Baez (Feb 20 2021 at 23:47):Fawzi Hreiki said:
Stuart Kurtz, a prominent complexity theorist, said in a poll of academics on the question: "Knowing Ketan Mulmuley, I live in fear that the solution will be via algebraic geometry, and it will come soon enough that I’ll be expected to understand it. An alternative nightmare is that the undergraduate who solves it will publish his solution in French."
Poor baby! He wants the solution to be in English, using math he already knows.
John Baez (Feb 20 2021 at 23:48):This remark should be enough to make French algebraic geometers solve P = NP.
José Siqueira (Feb 21 2021 at 11:26):I just love Mitsu Ogihara's story haha Sounds about right.
Matteo Capucci (he/him) (Feb 22 2021 at 08:58):I cheer for the 'undecidable' side :laughing: P vs NP seems too fundamental to be true or false on the nose. I guess it'll blow our mind like Godel undecidability of consistency of PA.
Or am I unware of some proof of decidability?
Morgan Rogers (he/him) (Feb 22 2021 at 09:25):A proof of decidability would just be a proof one way or the other :stuck_out_tongue_wink:
Matteo Capucci (he/him) (Feb 22 2021 at 14:03):Morgan Rogers (he/him) said:
A proof of decidability would just be a proof one way or the other :stuck_out_tongue_wink:
Really? A constructive proof certainly would.
Fawzi Hreiki (Feb 22 2021 at 14:08):I think it’s near impossible that someone will prove P = NP by non-constructively proving that a polynomial time algorithm exists for an NP-hard problem
Fawzi Hreiki (Feb 22 2021 at 14:08):I don’t even know what that would mean
Jules Hedges (Feb 22 2021 at 14:11):I can totally imagine that, but there are problems that it's known can't be independent because of their location in the arithmetic hierarchy (I think...... going by extremely hazy memory here). For example I think it's known that the Riemann hypothesis is not independent of ZFC (??)... hm, now I'm doubting myself
Morgan Rogers (he/him) (Feb 22 2021 at 14:42):Matteo Capucci (he/him) said:
Morgan Rogers (he/him) said:
A proof of decidability would just be a proof one way or the other :stuck_out_tongue_wink:
Really? A constructive proof certainly would.
I wouldn't be surprised if the nature of the problem is such that any proof of decidability can be applied to a suitably formulated NP-complete problem to yield a proof one way or the other. On the other hand, I'm not sure a non-constructive proof one way or the other would convince the community that the problem was resolved, so I expect any proof would be constructive enough for a typical computer scientist by default.
John Baez (Feb 22 2021 at 16:48):Anyway, there's no proof that P vs NP is decidable, and there's a lot of speculation that it's not. The Raborov-Rudich argument comes within shooting distance of showing that P vs NP is not decidable - though it really just says that if there were a "natural" proof, in a certain technical but interesting sense of "natural", then pseudorandom number generators could not exist.
James Wood (Feb 22 2021 at 19:25):I forget: why are P vs NP and logic Zulip in the same thread? Anyway, I was going to ask whether anyone knew the Π/Σ-number of P = NP off the top of their head.
Morgan Rogers (he/him) (Feb 22 2021 at 19:37):@James Wood good point, fixed, although we even got off the subsidiary topic heh
Oh and it was my fault that the topic diverged again! Oops
John Baez (Feb 22 2021 at 20:15):James Wood said:
Anyway, I was going to ask whether anyone knew the Π/Σ-number of P = NP off the top of their head.
I didn't know - I had to look it up. P NP is a sentence:
https://rjlipton.wordpress.com/2009/05/27/arithmetic-hierarchy-and-pnp/
John Baez (Feb 22 2021 at 20:17):Nobody knows if it can be written as a sentence.
James Wood (Feb 22 2021 at 20:22):I'm pretty sure the story in that blog post, true or not, is supposed to be about the predecessor rather than the successor.
John Baez (Feb 22 2021 at 20:32):That seems more believable: could someone invent Church numerals without knowing how to compute the successor function in terms of Church numerals?
James Wood (Feb 22 2021 at 21:09):Looking at the comments, someone pointed it out in 2009, the author responded, but clearly it wasn't changed.