3 ms·

I was a bit taken aback to read that P/NP equality would imply we could compute: "What is the shortest program that in a small amount of time will output the co

I was a bit taken aback to read that P/NP equality would imply we could compute: "What is the shortest program that in a small amount of time will output the complete works of Shakespeare." since I thought it was proven that determining that some program was the shortest program with a specific output is in general non-computable (relative to some set of axioms, only a finite number of programs are provably the shortest ones producing their outputs.) Maybe the catch here is the "in a small amount of time"? Or maybe I misunderstood something about Chaitin's "elegant program" idea (where the elegant program for some string S is the shortest one producting S as output.[1])? I'd be interested in any resolution of this, since it seems unlikely Mr Aaronson would be making a mistake on this topic! [1] http://www.academia.edu/5838116/Is_incompleteness_a_serious_problem http://www.academia.edu/5838116/Is_incompleteness_a_serious_...

BrainInAJar 12y ago
Email him. In my experience he's fantastic about answering questions via email. Then post his reply here, I'm curious too.
rndn 12y ago
Perhaps it's the Bounded Halting Problem which is known to be NPC: http://www.inf.ed.ac.uk/teaching/courses/cmc/lecture6.pdf http://www.inf.ed.ac.uk/teaching/courses/cmc/lecture6.pdf
deleted 12y ago
[deleted]
emmab 12y ago
The term is "time-bound kolmogorov complexity". https://en.wikipedia.org/wiki/Kolmogorov_complexity https://en.wikipedia.org/wiki/Kolmogorov_complexity It's a reference to time-bound solomonoff induction: http://www.scholarpedia.org/article/Algorithmic_probability http://www.scholarpedia.org/article/Algorithmic_probability edit: also see http://math.uni-heidelberg.de/logic/merkle/ps/mfcs-2009.pdf http://math.uni-heidelberg.de/logic/merkle/ps/mfcs-2009.pdf
- ttctciyf 12y ago
  Thanks (and other repliers) for the links. I've some reading to do..

BrainInAJar 12y ago

Email him. In my experience he's fantastic about answering questions via email. Then post his reply here, I'm curious too.

rndn 12y ago

Perhaps it's the Bounded Halting Problem which is known to be NPC: http://www.inf.ed.ac.uk/teaching/courses/cmc/lecture6.pdf http://www.inf.ed.ac.uk/teaching/courses/cmc/lecture6.pdf

deleted 12y ago

[deleted]

emmab 12y ago

The term is "time-bound kolmogorov complexity". https://en.wikipedia.org/wiki/Kolmogorov_complexity https://en.wikipedia.org/wiki/Kolmogorov_complexity It's a reference to time-bound solomonoff induction: http://www.scholarpedia.org/article/Algorithmic_probability http://www.scholarpedia.org/article/Algorithmic_probability edit: also see http://math.uni-heidelberg.de/logic/merkle/ps/mfcs-2009.pdf http://math.uni-heidelberg.de/logic/merkle/ps/mfcs-2009.pdf

ttctciyf 12y ago
Thanks (and other repliers) for the links. I've some reading to do..