User loginNavigation 
Some questions concerning P != NPI am actually kind of perplexed by this. My understanding is that if P != NP there should exist problems in NP that are not in P that aren't NPcomplete but is the reverse also true? i.e. should there be a problem whose solution is in NP but not in P but not NPcomplete would this imply that P != NP? For example, it would seem to me at first blush that certain problems do fall in this class if one allows for imperfect knowledge of subroutine code (which occurs in practice). For example password cracking would be one assuming the verification subroutine runs in polynomial time. 1. It is in NP since one can nondeterministically guess all strings and verify each in P time. My understanding about this subject is limited however but it would seem that this problem is guaranteed to execute in O(P*exp) on a TM and P time on a NTM and there is no room for improvement on a TM why doesn't this show that P != NP? It seems like something that must have been considered by many people. Thanks in advance, P.S. I asked a CS professor already and he wasn't sure about it since it isn't his specialty. So I thought it might be worth asking on a general forum. By Carter Cheng at 20160406 18:46  LtU Forum  previous forum topic  next forum topic  other blogs  2286 reads

Browse archivesActive forum topics 
Recent comments
3 days 7 hours ago
3 days 13 hours ago
4 days 5 hours ago
4 days 12 hours ago
4 days 14 hours ago
4 days 19 hours ago
5 days 50 min ago
5 days 1 hour ago
5 days 4 hours ago
5 days 6 hours ago