Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > ANTON MAKHLIN:
All reports by Author Anton Makhlin:

TR13-007 | 8th January 2013
Bruno Bauwens, Anton Makhlin, Nikolay Vereshchagin, Marius Zimand

Short lists with short programs in short time

Revisions: 1

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 universal machine, it is possible to compute in polynomial time on ... more >>>




ISSN 1433-8092 | Imprint