Property testing and graphs (I)

12 minute read Published:

Property testing, graphs, and testing connectedness.
Introduction When trying to solve problems with computers, it’s generally important to understand both when and why it is that the problem you are trying to solve is hard. This is ostensibly so that you can be smart about trying to solve this problem in practice (maybe don’t spend a million bucks on AWS credits trying to factor large primes, e.g.), but many people (including myself) think that the abstract analysis of problem hardness is interesting in its own right.