Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The reference below shows if $n!$ is ultimately hard, then $P_{\mathbb{C}} \ne NP_{\mathbb{C}}$. Is there any implication about the case if $n!$ is easy?

On the intractability of Hilbert's Nullstellensatz and an algebraic version of "$NP \ne P$" (1996) by Michael Shub , Steve Smale.

share|improve this question
What do you mean by the complexity of $n!$? Do you mean the complexity of computing $n!$? What do you mean by $P_{\mathbb{C}}$? –  Qiaochu Yuan Jul 29 '12 at 17:29
I am considering the model by Shub and Smale ("On the intractability of HIlbert's Nullstellansatz and an algebraic version of "$NP \ne P$""). –  J.A Jul 29 '12 at 17:31
That would have been a useful thing to mention in your original question. Shub and Smale paper available here. –  MJD Jul 29 '12 at 17:46
There's no reverse implication, in that paper at least. The computation time of the sequence $n!$ only gives a lower bound for the Twenty Questions problem they set out. –  Luke Mathieson Jul 30 '12 at 1:44
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.