7 ms·
This was already posted here. It is fatally flawed in that, although the theoretical computing time is polynomial, the memory required grows exponentially.
by skykooler 13y ago
This was already posted here. It is fatally flawed in that, although the theoretical computing time is polynomial, the memory required grows exponentially.
- topynate 13y agoI'm confident that the paper is indeed flawed. However, a Turing machine can neither write to nor read from an exponential number of locations in polynomial time, so the flaw will be something else.
- jmpe 13y agoMemory growth is not a consideration in the academic proof, Turing machine tape is infinite in both directions.
- taejo 13y agoTuring 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.
- deleted 13y ago[deleted]
- jessaustin 13y agoIn addition to what siblings said, remember that P is a subset of PSPACE.
- Gurkenglas 13y agoI think the statement you meant to remind us of is that NP is a subset of PSPACE.
- jessaustin 13y agoAccording to the paper under discussion, the two statements are equivalent. Your version is probably more graceful, however.
- skj 13y agoThis statement is not quite coherent. If there is an exponential memory growth, then there is exponential computing time because memory growth doesn't happen magically.
- ronaldx 13y agoSince P refers to polynomial time, it's not clear to me that a memory requirement is relevant.
- heron87 13y agoA definition of P indeed does not require a restriction on memory use. But the definition implies a restriction on memory: a polynomially bounded (in time) machine cannot use exponential memory (because reading 2^n cells on a tape requires 2^n time steps).
- ronaldx 13y agoSo an exponential memory requirement implies that the theoretical time is not polynomial after all? I'm not sure. It seems possible that I would need to have exponential memory but not necessarily to access it. Is it true to say that memory not-accessed is not-needed? It's believable but not immediately obvious to me, and if it's false then there's no two-way implication. Edit: apparently NP is a subset of PSPACE, so fair enough.
- heron87 13y agoNot sure what you mean by "memory requirement" and "theoretical time". If you don't access the memory, what do you mean by saying you "need" it? If a turing machine — or a computer program, for that matter — uses, i.e., "visits", exponentially many memory cells, then, indeed, its computing time cannot be polynomial. But note that every turing machine theoretically has infinite memory. The question is how much of it is actually used. PSPACE consists of those problems that can be solved by a turing machine that uses no more than p(n) memory, where p(n) is some polynomial in the input length n. Note that, for PSAPCE, time is unrestricted. So obviously P and NP are subsets of PSPACE, but it is unknown whether they are proper subsets.