We show that sets consisting of strings of high Kolmogorov complexity provide examples of sets that are complete for several complexity classes under probabilistic and non-uniform reductions. These sets are provably not complete under the usual many-one reductions.
Let RK; RKt; RKS;RKT be the sets of strings x having complexity at least {{\left| x \right|} \mathord{\left/ {\vphantom {{\left| x \right|} 2}} \right. \kern-\nulldelimiterspace} 2}, according to the usual Kolmogorov complexity measure K, Levin?s time-bounded Kolmogorov complexity Kt [27], a space-bounded Kolmogorov measure KS, and the time-bounded Kolmogorov complexity measure KT that was introduced in [4], respectively.
Our main results are:
1. RKS and RKt are complete for PSPACE and EXP, respectively, under P/poly-truth-table reductions. 2. EXP = NPRKt. 3. PSPACE = ZPP^{R_{ks} } \subseteq P^{R_k }. 4. The Discrete Log, Factoring, and several lattice problems are solvable in BPPRKT.
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb