computation theory - Kolmogorov complexity is uncomputable using reductions -


can please give me proof of k-complexity unsolvable using reductions.

eg:

pcp(2) <= pcp(3)

i can prove pcp(3) unsolvable reducing pcp(2) (by mapping every instance).

i not sure how reduce k-complexity known undecidable problem (like halting problem). i.e., x <= k-complexity

can please provide me proof that? @ least provide me idea (x ).

thanks in advance


Comments

Post a Comment

Popular posts from this blog

python - Installing PyDev in eclipse is failed -

unable read repository @ http://pydev.sf.net/updates/content.xml. sun.security.validator.validatorexception: pkix path building failed: sun.security.provider.certpath.suncertpathbuilderexception: unable find valid certification path requested target i installing pydev in eclipse using python, doesn't install successfully. gives above error. happened? how solve error? i had error when trying install on laptop behind corporate firewall. couldn't tell setup of firewall, not sure of root cause. i got passed error installing pydev eclipse when out behind firewall. another way got around have eclipse on non-firewalled machine, install pydev eclipse, , copy whole eclipse directory non-firewalled machine firewalled machine. there better way, , way fix properly, didn't have time work out firewall doing. this on windows 7 machine (yeah know) not work *nix versions installed through package manager yum or apt.
Read more

PHP OOP-based login system -

lets building oop-based user authentication system, , incorporate following principles: direct injection, inheritance, encapsulation, polymorphism , single responsibility principle. my background in programming has relied on procedural programming, , thus, finding difficult put these practices correct use. assume have these classes: class config { public function set($key, $value); public function get($key, $default = null); } class user { public function __construct(pdo $dbh, $id = null); public function setprofile(profile $profile); } class auth { public function __construct(config $config); public function login($username, $password, $keeploggedin = true); public function isloggedin(); public function getloggedinuser(); public function logout(); public function register(array $data); } class session { public function start($sessionname = null); public function write($key, $value); public function read($key, $default =...
Read more

c# - Nested Internal Class with Readonly Hashtable throws Null ref exception.. on assignment -

in internal game class , have both a) defined nested internal gamertags class , b) defined gamertags[] _array variable. in internal gamertags class (the nested class, simplicity left out) have readonly hashtable . after initialization, still null ref exception when try assign value. i'm not changing pointer value only , need add initialization hastable? internal class gamertags { private readonly hashtable _privatereadonlyhashtable; private string _json; private string _hash; internal idictionary privatereadonlyhashtable { { return this._privatereadonlyhashtable; } } internal string hash { { this.ensurehash(); return this._hash; } } internal object this[string key] { { return this._privatereadonlyhashtable[k...
Read more