Hacker News Reader

Restricting the problem to a fixed size input makes factoring an O(1) operation; so I still don't see what all the fuss is about.

Unless you know a way of extending this to handle an arbitrary amount of I/O then it's just a way of implementing nondeterministic finite state machines; which are no more powerful than deterministic finite state machines.

View on HN

Rather than downvoting you to oblivion, I'll point out that "Restricting the problem to a fixed size input makes factoring an O(1) operation" makes no sense. Sorting an array of N items using a comparison sort has a lower complexity bound of O(N log(N)) in the worst case. Yes, of course that becomes O(1) if you say N is constant, but that's really not helpful at all.

Reply on news.ycombinator.com