Path: utzoo!yunexus!ists!helios.physics.utoronto.ca!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!think!yale!quasi-eli!cs.yale.edu!blenko-tom
From: blenko-tom@CS.YALE.EDU (Tom Blenko)
Newsgroups: comp.lang.prolog
Subject: Re: Hype about Prolog
Message-ID: <25290@cs.yale.edu>
Date: 29 May 90 15:53:08 GMT
Article-I.D.: cs.25290
References: <2550@randvax.UUCP> <21552@megaron.cs.arizona.edu> <2554@randvax.UUCP>
Sender: news@cs.yale.edu
Reply-To: blenko-tom@CS.YALE.EDU (Tom Blenko)
Organization: Yale University Computer Science Dept, New Haven CT  06520-2158
Lines: 22

In article <2554@randvax.UUCP> narain@randvax.UUCP (Sanjai Narain) writes:
|Of course, the difficulty of reasoning about non-deterministic algorithms
|depends upon the algorithm. What I said was that by expressing these
|in logic, one can reason about them the same way as one reasons about
|other sentences in logic. For example, it is quite easy to show that
|the following non-deterministic program:
|
|	subset([],[]).
|	subset([U|V],Z):-subset(V,Z).
|	subset([U|V],[U|Z]):-subset(V,Z).
|
|will compute exactly 2**n subsets of a set of length n (represented as
|a list), and whose complexity is O(2**n) SLD-resolution steps.

I don't understand. I don't expect this program to terminate for the
query

	subset(X,1)

so perhaps it is not so easy to show? Or if so, how?

	Tom