News for hackers. Stuff that matters.

A comment on P = NP. Parent comment

Re:P = NP by jmpe on Wednesday December 04, 2013 @06:59AM (#6846343)
Memory growth is not a consideration in the academic proof, Turing machine tape is infinite in both directions.
[ Parent | on HN ]
Re:P = NP by taejo on Wednesday December 04, 2013 @07:08AM (#6846372)
Turing machines have may have infinite memory, but they can also only write one step per cell. So a polynomial-time TM can't use superpolynomial memory.
[ Parent | on HN ]