Homogeneous measures and polynomial time invariants
- 1 January 1988
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
The usual probability distributions are concentrated on strings that do not differ noticeably in any fundamental characteristics, except their informational size (Kolmogorov complexity). The formalization of this statement is given and shown to distinguish a class of homogeneous probability measures suggesting various applications. In particular, it could explain why the average case NP-completeness results are so measure-independent and could lead to their generalization to this wider and more invariant class of measures. It also demonstrates a sharp difference between recently discovered pseudorandom strings and the objects known before.Keywords
This publication has 9 references indexed in Scilit:
- Random instances of a graph coloring problem are hardPublished by Association for Computing Machinery (ACM) ,1988
- One way functions and pseudorandom generatorsCombinatorica, 1987
- Expanders obtained from affine transformationsCombinatorica, 1987
- How to construct random functionsJournal of the ACM, 1986
- How to Generate Cryptographically Strong Sequences of Pseudorandom BitsSIAM Journal on Computing, 1984
- Theory and application of trapdoor functionsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1982
- How to generate cryptographically strong sequences of pseudo random bitsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1982
- Explicit constructions of linear-sized superconcentratorsJournal of Computer and System Sciences, 1981
- A formal theory of inductive inference. Part IInformation and Control, 1964