Thanks! This is indeed related and part of my inspiration for this question.

Some other interesting references:

- The waterfall argument in paragraph 6 of the mind-boggling "Why Philosophers Should Care About Computational Complexity". https://www.scottaaronson.com/papers/philos.pdf

- "NP-complete Problems and Physical Reality" https://www.scottaaronson.com/papers/npcomplete.pdf