A theoretical computer science problem that the SOTA LLMs get wrong (as of now)
In my graduate-level complexity theory class, I came across the concept of a P-splinter, an incredibly niche complexity class that is used in a few papers. Intuitively, a P-splinter is a language where a PTIME function can enumerate its elements. This concept was defined by Lane A. Hemachandra—who is…