I have a collection of results and links to relevant papers in this blog post: https://pron.github.io/posts/correctness-and-complexity