Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR06-125 | 20th September 2006 00:00

Low-Depth Witnesses are Easy to Find

RSS-Feed




TR06-125
Authors: Luis Antunes, Lance Fortnow, Alexandre Pinto, Andre Souto
Publication: 28th September 2006 13:47
Downloads: 1179
Keywords: 


Abstract:

Antunes, Fortnow, van Melkebeek and Vinodchandran captured the
notion of non-random information by computational depth, the
difference between the polynomial-time-bounded Kolmogorov
complexity and traditional Kolmogorov complexity We show how to
find satisfying assignments for formulas that have at least one
assignment of logarithmic depth. The converse holds under a
standard hardness assumptions though fails if BPP = UP = EXP.

We also show that under standard hardness assumptions one cannot
increase the depth of a string efficiently and that such
an assumption is required.



ISSN 1433-8092 | Imprint