Talk:Sub-exponential time

Contested Speedy

I've added some context, and this page is now linked to by one other page. More links can easily be added to here, and content relating to complexity theory can easily be added in time. I suggest this be left for a while to see if it develops into a useful article. Verbal chat 10:10, 30 July 2008 (UTC)

Suggestions

Some suggestions:

• Perhaps we should move the general number field sieve example somewhere else from the lead. In the current version, the first formula of the lead is $O(2^{{(\log N)}^{1/3}})$, which is highly misleading, as this is not sub-exponential in N.
• We could mention the classes QP and SUBEXP in the text. (I have already created redirects QP (complexity) and SUBEXP.)
• More concrete examples. It's a bit tricky to get any intuition about formulas such as $2^{O((\log n)^{c})}$. We could mention that if c = 1 then this is simply poly(n). And point out that while running times like n¹⁰ or 10^ln n are polynomial, things like n^ln n are quasi-polynomial.
• To make things absolutely clear, perhaps we could also have a table with four rows: polynomial, quasi-polynomial, sub-exponential and exponential. A bit like taking 4 rows from Big O notation#Orders of common functions (without the examples).

— Miym (talk) 09:27, 2 December 2009 (UTC)

I've implemented the first suggestion, and stated all complexities in the size of the input. I've defined QP. But it seems that the definition of SUBEXP used here differs from that used on the complexity zoo. The zoo's definition defines a bigger class of algorithms. I'm not sure which is the canonical definition of SUBEXP.

The table idea is good, perhaps with concrete examples being included in the table itself? But go ahead and make a table however you like.

Robin (talk) 13:51, 2 December 2009 (UTC)

OK, so I did some searching. It seems that SUBEXP is always defined the way it is on the complexity zoo. Moreover, with this definition the class is robust under polynomial sized changes in input encoding. Also see a long discussion on this topic on Scott Aaronson's blog [1]. --Robin (talk) 02:50, 3 December 2009 (UTC)

The article is in a pretty good shape now, thanks for your efforts! Perhaps we should also fix Big O notation#Orders of common functions accordingly? — Miym (talk) 09:15, 3 December 2009 (UTC)