ECCC-Report TR10-091https://eccc.weizmann.ac.il/report/2010/091Comments and Revisions published for TR10-091en-usFri, 28 May 2010 13:09:19 +0300
Paper TR10-091
| An Encoding Invariant Version of Polynomial Time
Computable Distributions |
Nikolay Vereshchagin
https://eccc.weizmann.ac.il/report/2010/091When we represent a decision problem,like CIRCUIT-SAT, as a language over the binary alphabet,
we usually do not specify how to encode instances by binary strings.
This relies on the empirical observation that the truth of a statement of the form ``CIRCUIT-SAT belongs to a complexity class $C$''
does not depend on the encoding, provided both the encoding and the class $C$ are ``natural''. In this sense most of the Complexity theory is ``encoding invariant''.
The notion of a polynomial time computable distribution from
Average Case Complexity is one of the exceptions from this rule.It might happen that a distribution over some objects, like circuits,is polynomial time computable in one encoding and is not polynomial time computable in the other encoding.
In this paper we suggest an encoding invariant
generalization of a notion of a polynomial time computable
distribution. The completeness proofs of known distributional
problems, like Bounded Halting,
are simpler for the new class than for polynomial time computable distributions.
This paper has no new technical contributions. All the statements are proved using the known techniques. Fri, 28 May 2010 13:09:19 +0300https://eccc.weizmann.ac.il/report/2010/091