home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / theory / 1862 < prev    next >
Encoding:
Text File  |  1992-09-03  |  1.3 KB  |  43 lines
  1. Newsgroups: comp.theory
  2. Path: sparky!uunet!haven.umd.edu!darwin.sura.net!sgiblab!news.cs.indiana.edu!lynx!nmsu.edu!opus!gupta
  3. From: gupta@nmsu.edu (Gopal Gupta)
  4. Subject: A question
  5. Message-ID: <1992Sep3.225109.24782@nmsu.edu>
  6. Sender: usenet@nmsu.edu
  7. Organization: NMSU Computer Science
  8. Date: Thu, 3 Sep 1992 22:51:09 GMT
  9. Lines: 32
  10.  
  11.  
  12. Can anyone help me with the following problem. An actual
  13. proof or a reference to a paper where I can find the proof
  14. will be most helpful. Thanks.
  15.  
  16. Consider the following sequential program:
  17.  
  18.         begin
  19.                 (1) input a finite set of integers S;
  20.                 (2) find an x in S such that some fixed property P(x) is true;
  21.                 (3) output x
  22.         end.
  23.  
  24.         Question:  Can the search in step 2 be done in number of steps
  25.                 independent of the size of S?   If so, how?  If not, how do
  26.                 you prove it?    (Ignore time to compute P(x).)
  27.  
  28.  
  29. Please reply by email, as I don't read this newsgroup often.
  30.  
  31. Thank you.
  32.  
  33. Gopal Gupta
  34. ---------------------------------------------------------------------
  35. Department of Computer Science       email: gupta@nmsu.edu
  36. Box 30001, Dept. CS                    gupta@compsci.bristol.ac.uk
  37. New Mexico State University       Ph: +1 (505) 646 6236 
  38. Las Cruces, NM 88003-0001       Fax: +1 (505) 646 6218
  39. USA
  40. ---------------------------------------------------------------------
  41.  
  42.      
  43.