Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR04-082 | 9th September 2004
Olaf Beyersdorff

Representable Disjoint NP-Pairs

Revisions: 1

We investigate the class of disjoint NP-pairs under different reductions.
The structure of this class is intimately linked to the simulation order
of propositional proof systems, and we make use of the relationship between
propositional proof systems and theories of bounded arithmetic as the main
tool of our analysis.
more >>>


TR04-081 | 9th September 2004
Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolay Vereshchagin

Increasing Kolmogorov Complexity

How much do we have to change a string to increase its Kolmogorov complexity. We show that we can
increase the complexity of any non-random string of length n by flipping O(sqrt(n)) bits and some strings
require
Omega(sqrt(n)) bit flips. For a given m, we also give bounds for ... more >>>


TR04-080 | 7th September 2004
Lance Fortnow, Troy Lee, Nikolay Vereshchagin

Kolmogorov Complexity with Error

We introduce the study of Kolmogorov complexity with error. For a
metric d, we define C_a(x) to be the length of a shortest
program p which prints a string y such that d(x,y) \le a. We
also study a conditional version of this measure C_{a,b}(x|y)
where the task is, given ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint