Distinguishing Complexity and Symmetry of Information
Harry Buhrman, Lance Fortnow · 1995
We describe how to use polynomial-time Kolmogorov distinguishing complexity to give an approximate measure of the size of sets. For any set S, we show that relative to S the polynomial time distinguishing complexity of every element of length n of S is bounded by 2 log jjS =n jj + O(log n). This lemma enables us to give a characterization of sparse sets using distinguishing complexity. We use this new lemma as a catalyst to study symmetry of information for polynomial-time distinguishing complexity. Longpr'e and Mocas and Longpr'e and Watanabe showed that if certain one-way functions exist then symmetry of information fails for the standard polynomial-time Kolmogorov complexity. We try to recover symmetry of information by studying Kolmogorov distinguishing complexity using our new approximating measure idea to avoid the problems with one-way functions and indexing of strings in (small) sets. We show problems with even formalizing the symmetry of information question for polynomial-...