home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #19 / NN_1992_19.iso / spool / comp / theory / 1838 < prev    next >
Encoding:
Internet Message Format  |  1992-08-30  |  769 b 
  1. Path: sparky!uunet!europa.asd.contel.com!darwin.sura.net!gatech!rutgers!ub!acsu.buffalo.edu!guest13
  2. From: guest13@acsu.buffalo.edu (Javaid Aslam)
  3. Newsgroups: comp.theory
  4. Subject: NC-Completeness of Transitive Closure
  5. Keywords: NC-completeness, NC-reduction
  6. Message-ID: <BttLv9.Ao5@acsu.buffalo.edu>
  7. Date: 30 Aug 92 23:42:45 GMT
  8. Sender: nntp@acsu.buffalo.edu
  9. Organization: UB
  10. Lines: 10
  11. Nntp-Posting-Host: garuth.eng.buffalo.edu
  12.  
  13. I have this conjecture which might be refuted with some contradicting
  14. evidence. Hope somebody can provide me at least some insight why this
  15. can not be true:
  16.  
  17. Conjecture: The Transitive Closure problem is complete for the class NC
  18.             (with respect to some "NC-reduction").
  19.  
  20. Thank you all ..
  21.  
  22.  -Javaid Aslam : guest13@eng.buffalo.edu
  23.