home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / sci / logic / 2064 < prev    next >
Encoding:
Internet Message Format  |  1992-11-16  |  1.0 KB
  1. Xref: sparky sci.logic:2064 sci.math:15068
  2. Newsgroups: sci.logic,sci.math
  3. Path: sparky!uunet!stanford.edu!CSD-NewsHost.Stanford.EDU!Sunburn.Stanford.EDU!pratt
  4. From: pratt@Sunburn.Stanford.EDU (Vaughan R. Pratt)
  5. Subject: Re: Logic and Mathematicians
  6. Message-ID: <1992Nov16.193017.25867@CSD-NewsHost.Stanford.EDU>
  7. Sender: news@CSD-NewsHost.Stanford.EDU
  8. Organization: Computer Science Department,  Stanford University.
  9. References: <1992Nov15.191744.17481@husc3.harvard.edu> <1992Nov16.050846.15982@infodev.cam.ac.uk> <1992Nov16.165221.5725@guinness.idbsu.edu>
  10. Date: Mon, 16 Nov 1992 19:30:17 GMT
  11. Lines: 9
  12.  
  13. In article <1992Nov16.165221.5725@guinness.idbsu.edu> holmes@garnet.idbsu.edu (Randall Holmes) writes:
  14. >This is exactly what I was thinking about.  There would also have to
  15. >be some algorithm that one could not prove to not be in P.  Would this
  16. >algorithm have to be "objectively" in P?
  17.  
  18. P consists of sets, not algorithms.  A slow algorithm says nothing
  19. about the complexity of the set it accepts.
  20. -- 
  21. Vaughan Pratt              A fallacy is worth a thousand steps.
  22.