Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!tut.cis.ohio-state.edu!zaphod.mps.ohio-state.edu!usc!randvax!narain
From: narain@randvax.UUCP (Sanjai Narain)
Newsgroups: comp.lang.prolog
Subject: Re: Hype about Prolog
Message-ID: <2565@randvax.UUCP>
Date: 30 May 90 18:23:51 GMT
References: <2550@randvax.UUCP> <21552@megaron.cs.arizona.edu> <2554@randvax.UUCP> <25290@cs.yale.edu>
Organization: Rand Corp., Santa Monica, Ca.
Lines: 26

# |
# |     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

The SLD-search tree for the query subset([a1,..,an],Z), Z a variable, will
consist of O(2**n) branches. Let this number of branches be F(n).
Then, F(n+1)=2*F(n)+2. This is because the query subset([a1,..,an+1],Z)
yields two branches, each ending in subset([a1,..,an]). Solving this
recurrence yields F(n) = 3*2**n - 2. Correctness can be proved similarly,
in particular, by observing that each statement is a correct fact about
the subset relation.

Sanjai Narain