2013/01/08 by Bruno Bauwens, Bauwens, Bruno, Anton Makhlin +5 · 2 voices
Computer Science · #03D15 #03D25 #05C70 #05C85 #68Q17 #68Q30 #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #F.1.2 #F.2 #FOS: Computer and information sciences #G.2.2 #acm:03D15 #acm:03D25 #acm:05C70 #acm:05C85 #acm:68Q17 #acm:68Q30 #cs.CC #cs.DS #msc:03D15 #msc:03D25 #msc:05C70 #msc:05C85 #msc:68Q17 #msc:68Q30
paper · pdf · doi:10.48550/arxiv.1301.1547
arxiv published 2013/01/08 · arxiv created 2017/03/30 · arxiv updated 2017/03/31
Given a machine U, a c-short program for x is a string p such that U(p)=x and the length of p is bounded by c + (the length of a shortest program for x). We show that for any standard Turing machine, it is possible to compute in polynomial time on input x a list of polynomial size guaranteed to contain a O(log |x|)-short program for x. We also show that there exists a computable function that maps every x to a list of size |x|2 containing a O(1)-short program for x. This is essentially optimal because we prove that for each such function there is a c and infinitely many x for which the list has size at least c|x|2. Finally we show that for some standard machines, computable functions generating lists with 0-short programs, must have infinitely often list sizes proportional to 2|x|.