home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / comp / theory / 2696 < prev    next >
Encoding:
Internet Message Format  |  1992-12-14  |  1.6 KB
  1. Path: sparky!uunet!mcsun!sunic!dkuug!diku!torbenm
  2. From: torbenm@diku.dk (Torben AEgidius Mogensen)
  3. Newsgroups: comp.theory
  4. Subject: Re: 2 stack PDA and other questions
  5. Message-ID: <1992Dec14.113827.686@odin.diku.dk>
  6. Date: 14 Dec 92 11:38:27 GMT
  7. References: <1992Dec13.162048.14632@miavx1.acs.muohio.edu>
  8. Sender: torbenm@thor.diku.dk
  9. Organization: Department of Computer Science, U of Copenhagen
  10. Lines: 30
  11.  
  12. khmak@miavx1.acs.muohio.edu writes:
  13.  
  14. >A few days ago someone posted a few questions that I was also curious about
  15. >knowing the answer to.  Here they are:
  16.  
  17.  
  18. >Why is a 2 stack PDA equivalent to a turing machine?
  19.  
  20. Because one stack can hold the contents of the tape to the left of the
  21. pointer, and the other stack can hold the portion of the tape to the
  22. right of the pointer. Thus, a TM is easy to simulate.
  23.  
  24. >Why is it important to know if there is at least one decision problem that is
  25. >undecidable?
  26.  
  27. Importance depends on who you are. Many programmers life happily
  28. without knowing about the unsolvability of the halting problem, but if
  29. you have one specific problem that you know is undecidable, you can
  30. often use this to prove the undecibability of other problems.
  31.  
  32. >Who cares if P=NP?  Or what is the significance of the question "Is P=NP"?
  33.  
  34. If P=NP then there exist efficient algorithms to solve problems, where
  35. the best known current algorithms are so inefficient that it is
  36. unrealistic to solve certain problems. There was/is a discussion (in
  37. comp.theory or sci.math) about the consequence for "unbreakable"
  38. codes. In essence, the point is that if P=NP it is impossible to make
  39. a code that it takes exponential time to break.
  40.  
  41.     Torben Mogensen (torbenm@diku.dk)
  42.