home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / theory / 1839 < prev    next >
Encoding:
Text File  |  1992-08-30  |  1.1 KB  |  33 lines
  1. Newsgroups: comp.theory
  2. Path: sparky!uunet!cs.utexas.edu!tamsun.tamu.edu!chen
  3. From: chen@cs.tamu.edu (Jianer Chen )
  4. Subject: Re: NC-Completeness of Transitive Closure
  5. Message-ID: <1992Aug31.020830.21790@tamsun.tamu.edu>
  6. Keywords: NC-completeness, NC-reduction
  7. Sender: news@tamsun.tamu.edu (Read News)
  8. Organization: Computer Science Department, Texas A&M University
  9. References: <BttLv9.Ao5@acsu.buffalo.edu>
  10. Date: Mon, 31 Aug 1992 02:08:30 GMT
  11. Lines: 20
  12.  
  13. In article <BttLv9.Ao5@acsu.buffalo.edu> guest13@acsu.buffalo.edu (Javaid Aslam) writes:
  14. >I have this conjecture which might be refuted with some contradicting
  15. >evidence. Hope somebody can provide me at least some insight why this
  16. >can not be true:
  17. >
  18. >Conjecture: The Transitive Closure problem is complete for the class NC
  19. >            (with respect to some "NC-reduction").
  20. >
  21. >Thank you all ..
  22. >
  23. > -Javaid Aslam : guest13@eng.buffalo.edu
  24.  
  25. It is easy to show that NC has no complete problems with respect to 
  26. any NC-reduction (as long as the reduction is in NC^k for some k) 
  27. unless the NC hierarchy collapses, which is a very strong 
  28. consequence. 
  29.  
  30. --- JC
  31.  
  32.  
  33.