Analysis of Algorithms and Partial Algorithms

IAFF-User-131

Analysis of Algorithms and Partial Algorithms

post by IAFF-User-131 (Imported-IAFF-User-131) · 2016-02-04T00:15:55.000Z · LW · GW · 3 comments

This is a link post for http://arxiv.org/abs/1601.03411

3 comments

Comments sorted by top scores.

comment by IAFF-User-131 (Imported-IAFF-User-131) · 2016-04-17T15:43:53.000Z · LW(p) · GW(p)

I just read Jim Babcock's post https://agentfoundations.org/item?id=374 and realized how similar math oracles are to 0' algorithms and strengths are to scores.

comment by Vanessa Kosoy (vanessa-kosoy) · 2016-02-21T14:58:27.000Z · LW(p) · GW(p)

The mean running time is usually not used in average-case complexity theory because it is not well-behaved under changing the model of computation. Your $(n!)!$ example is in the class $H e u r_{n e g} P$ . For a good overview of average-case complexity theory see Bogdanov and Trevisan.

Replies from: Imported-IAFF-User-131

↑ comment by IAFF-User-131 (Imported-IAFF-User-131) · 2016-02-25T00:15:09.000Z · LW(p) · GW(p)

Thanks for that info! Uniform distributions are, however, generally used in analysis of algorithms, which is a different field from complexity theory.