Complexity and Infinity

by · Jan 23, 2014 · 2,750 views ·

Pražský informatický seminář

When the set theory was axiomatized, the guiding principle was to keep as many properties of finite sets as possible also for infinite sets. Today, lacking methods to solve problems in complexity theory, we are, in a sense, doing the opposite: we make conjectures about finite structures using facts that are true about similar infinite structures. For example, our belief that P ≠ NP is mainly supported by the fact that recursively enumerable sets are not recursive. I will give some examples of such conjectures in complexity theory and mention some results that can be viewed as corroboration of their validity. These examples come from proof complexity – a field that studies complexity from the perspective of logic – but these conjectures can also be stated in purely computational terms. One of the conjectures is that there is no complete problem for a certain class of search problems.