Post

Colin
@colin-fraser.net

What do people make of all these conjectured complexity bounds falling to AI by a hair’s breadth? Striking pattern, no?

0 reposts23 likes

Sotek
@sotekprime.bsky.social

Well, some of that is AI doing what is asked, not what is expected - the one of these I'm most informed about had massive improvements once people started dissecting the proof and applying the same technique but better. AI is doing the hard part then stopping instead of doing the easy followup.

Sotek
@sotekprime.bsky.social

What would the world look like if P != NP *but* peano arithmetic can't prove it? Embedding a proof system in a reduction such that it commits evil if the proof system proves it in P time? Seems hard to force it to still be a valid reduction after doing evil. Unless the evil is a runtime blowup?

Sotek
@sotekprime.bsky.social

Shit this is going to bug me because that is the same shape as proofs I know nobody but me was exploring a decade ago (I have the papers and PhD to prove it!) so if it would be valid there's a real chance nobody has tried it.