home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #18 / NN_1992_18.iso / spool / comp / ai / neuraln / 3254 < prev    next >
Encoding:
Text File  |  1992-08-20  |  1.1 KB  |  28 lines
  1. Newsgroups: comp.ai.neural-nets
  2. Path: sparky!uunet!usc!rpi!lima
  3. From: lima@moon.ral.rpi.edu (Pedro Lima)
  4. Subject: Question:Measuring complexity of CPU-time?
  5. Message-ID: <6ghyfh_@rpi.edu>
  6. Nntp-Posting-Host: moon.ral.rpi.edu
  7. Organization: Rensselaer Polytechnic Institute, Troy NY
  8. Date: Thu, 20 Aug 1992 19:44:02 GMT
  9. Lines: 17
  10.  
  11. The definition of Kolmogorov Complexity of a string s as the smallest program p
  12. that when presented as input to an Universal Turing Machine U outputs s 
  13. may cause practical problems since U is allowed to run p for any length of
  14. time as long as it eventually terminates. This time may of course be too
  15. long to be practical (think of a NP-complete problem). Thus, some authors
  16. define a time-bounded complexity where essentially U is restricted to
  17. terminate within T steps leaving s as output.
  18.  
  19. My question is: is there any problem to use in the definition of K-compl.
  20. the number of time-consuming operations (say flops) instead of the length
  21. in bits of the machine code of a program and thus consider computational
  22. time as a measure of complexity itself?
  23.  
  24. Thanks
  25.  
  26. Pedro Lima
  27. lima@ral.rpi.edu
  28.