Skip to main content

All Questions

Filter by
Sorted by
Tagged with
9 votes
4 answers
2k views

Computational complexity theoretic incompleteness: is that a thing?

Has anyone done research in an area that I have not heard of but that I want to call "Computational complexity theoretic incompleteness", which would mean not absolute incompleteness in the ...
Hank Igoe's user avatar
  • 193
16 votes
3 answers
1k views

Finite versions of Godel' s incompleteness

Assume you have some notion of proof complexity: for instance, at the basic level, the length of a proof, or the number of symbols used, take your pick (there are more involved measures, but for sake ...
Mirco A. Mannucci's user avatar