On 26 Sep 2008, at 19:18, Stephan Friedrichs wrote:
apfelmus wrote:
[..]
Persistent data structures are harder to come up with than ephemeral
ones, [...]
Yes, in some cases it's quite hard to find a persistent solution for a
data structure that is rather trivial compared to its ephemeral
counterpart. My question is: Is there a case, where finding a
persistent
solution that performs equally well is *impossible* rather than just
harder? I mean might there be a case where (forced) persistence (as we
have in pure Haskell) is a definite disadvantage in terms of big-O
notation? Do some problems even move from P to NP in a persistent
setting?
I'm fairly confident one could come up with a proof that you'll never
go from P to NP because of it along the lines of treating all memory
as being a list. Operations to modify memory are all in P (although
slow), so any algorithm that relies on mutation to be in P will stay
in P (although with a higher polynomial factor).
Bob
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
