[Haskell-cafe] Re: Red-Blue Stack

[Thomas Davie]

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