User loginNavigation 
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 (radixtree) 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. By Carter Cheng at 20120930 04:16  LtU Forum  previous forum topic  next forum topic  other blogs  8004 reads

Browse archivesActive forum topics 
Recent comments
8 hours 4 min ago
9 hours 27 min ago
10 hours 7 min ago
10 hours 31 min ago
11 hours 27 min ago
12 hours 17 min ago
18 hours 26 min ago
18 hours 59 min ago
19 hours 10 min ago
1 day 10 hours ago