Patrick Dubroy
@dubroy
Is there a general term for a function that is asymptotically more complex to solve, vs. verifying a solution?

It's related to P vs NP and one-way functions, but I'm taking about something like: O(n²) to solve and O(n) to check a solution.
Jan 26, 2022 · 4 · 1

Context —

I have a hunch that it's related to a useful definition of "declarative programming". The usual definition I've heard is "describe what you want to do, not how you want to do it" which imo is very vague.

Also related — "Defining syntactic sugar": loup-vaillant.fr/articles/synta…

https://twitter.com/dubroy/status/1486328681064714241 ∙ Archived on 2025-03-28.

← Twitter Archive: 2022