## User login## Navigation |
## archives## P = NP questionI was skimming through Sipser the other day and came across an anomaly I believe I may have encountered before (I think I recall reading this sometime in 1997 for the first time). It points to something I dont quite understand about the P = NP question so I decided to do some scribbling on a note pad and type it up in latex. The question I had points to the following: 1) Why don't TM based trie (radix-tree) like data structures trivially decide any language in O(n) time (and thus yield a trivial solution to P = NP since every deterministic Turing Machine is a nondeterministic one)? 2) If this is the case it would seem that there is something wrong with the definitions of NP and P in that having a DTM or NTM decide a language may not be strong enough to capture what someone means by a language. 3) There are obviously cases of languages that seem to be decided by algorithms which are in NP but not P. An example would be something like a generalized password cracking tool akin to John the Ripper(for those security gurus). I tossed it up on google docs here: https://docs.google.com/open?id=0B8BIjzf4onOFeFk2cVpyY3hkemM I am curious if there was anything wrong with my reasoning. |
## Browse archives## Active forum topics |

## Recent comments

2 hours 33 min ago

13 hours 31 min ago

19 hours 20 min ago

19 hours 40 min ago

20 hours 10 min ago

20 hours 56 min ago

21 hours 20 min ago

21 hours 48 min ago

23 hours 21 min ago

23 hours 46 min ago