Hacker News new | past | comments | ask | show | jobs | submit login

No, incompleteness and its generalizations fall within computability theory, not complexity theory.

In regard to your second point, you say "other problems in computational complexity". Again, you mentioned computability theory, not CCT. They are different endeavors. Aaronson was careful to say that this is not another essay on philosophy and computability.




Consider applying for YC's Spring batch! Applications are open till Feb 11.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: