Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > COMPLETENESS PROOFS:
Reports tagged with completeness proofs:
TR10-091 | 14th May 2010
Nikolay Vereshchagin

An Encoding Invariant Version of Polynomial Time Computable Distributions

When 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$''
more >>>




ISSN 1433-8092 | Imprint