From the logicians I learned about K-trivial sets. Let K(x) be the prefix-free Kolmogorov complexity of x, i.e., the size of the smallest program that generates x. There are several equivalent definitions of K-trivial sets, here is two of them. A are K-trivial if
- For some constant c, for all x, K(x) ≤ KA(x)+c, where KA(x) is the smallest program generating x with access to oracle A.
- For some constant c, for all n, K(A1:n) ≤ K(n)+c, where A1:n are the first n bits of the characteristic sequence of A.
- All computable sets are K-trivial and there are K-trivial sets that are not computable.
- There are only a countable number of K-trivial sets. In fact there are only a finite number of K-trivial sets for each fixed constant c above.
- Every K-trivial set is super-low, that is the halting problem relative to a K-trivial set is non-adaptively reducible to the halting problem.
- Every K-trivial non-adaptively reduces to a computably-enumerable set.
- Every set reducible to a K-trivial is K-trivial.
- The disjoint union of two K-trivial sets is K-trivial.
- Random sets are still random relative to A.
More about K-trivial sets and everything else computably random in a great book by Downey and Hirschfeldt.
Us complexity theorists started thinking about polynomial-time versions of K-trivial sets but probably won't have as many nice properties.
Is there a result in Complexity Theory such that its statement has nothing to do with Kolmogorov Complexity, yet its proof uses Kolmogorov Complexity in a critical way?
ReplyDeleteIgnorant question (and I'm legitimately curious, not trying to be smarmy), what do computability researchers research these days? Are there new results? I always thought (or at least have read, not being in academia I don't have my own view on this) that computability theory has been stagnant for quite a while and most "related" results are in complexity theory now. Obviously I see this view is wrong, but what's cooking on on that end of things?
ReplyDeleteDoesn't Robin Moser's proof of the LLL use Kolmogorov complexity?
ReplyDeleteTwo big non-stagnant topics in computability theory:
ReplyDelete1) Reverse Mathematics- using computability theory to pin down
how constructive certain theorems in math are. Here Computability
theory is a tool for something else. (An earlier program which
is more obviously using computability theory is Nerode's
Recursive Mathematics program). For more see Stephen Simpson's home page.
2) Random sets, as Lance is talking about. That Superlow=K-trivial
is a very nice result that connects the two fields. For more
see Downey-Hirschfeld.
CORRECTION- my comment said Superlow=K-trivial.
ReplyDeleteActually its K-Trivail is proper Subset of Superlow.
Rod Downey emailed me the corrections for which I thank him.
Attending this meeting it seemed to me that the computability school of K-complexity is slowly taking over the complexity school, with the majority of young people present studying computability aspects of K-complexity.
ReplyDeleteI don't know if this an accurate description of the actual state of K-complexity, e.g. it may be due to the mere fact that the majority of the organizers have a computability background.
I'm sure the organizers had good reasons, but I found the number of talks was on the low side, and I would have liked to hear more talks given the many "famous" people present.
Is there a result in Complexity Theory such that its statement has nothing to do with Kolmogorov Complexity, yet its proof uses Kolmogorov Complexity in a critical way?
ReplyDeleteIf you consider lower bounds as a hybrid between algorithms and complexity theory then there are tons of them.