Lambda the Ultimate

This probably isn't on topic for the site, but as a long time member, you probably already knew that!

i.e. should there be a problem whose solution is in NP but not in P but not NP-complete would this imply that P != NP?

So you're positing that there is a problem in NP but not P and are asking whether that implies that P != NP? Sets are only equal if they have the same elements, so yes :).

Sorry if it is a bit off topic. I wasn't too sure where to ask something like this. I guess the question becomes if guessing games like password cracking are valid when it comes to asking if P != NP. I guess I will maybe try posting somewhere else. Thanks.

It is rather straight forward to prove that it takes exp time to get the correct string in the worse case

I forgot a lot about the subject but the above is simply not true, or unknown, as I remember it.

I suppose its off topic but the question is not hard to answer.

Your main handwave, that invalidates the argument you suggest, is here:

It is rather straight forward to prove that it takes exp time to get the correct string in the worse case

and here:

if one allows for imperfect knowledge of subroutine code (which occurs in practice).

Please recall (or learn) that the question of P ?= NP is a question of the computational complexity of definite mathematical functions.

You say:

For example password cracking would be one assuming the verification subroutine runs in polynomial time.

Evidently, the mathematic function you have in mind takes as input a "verification subroutine".

Because you treat this subroutine as a vague type, you don't even have a way to talk meaningfully about the size of the subroutine.

Whether or not the deterministic password cracker program can operate in polynomial time relative to the size of the subroutine is what determines if the problem is or is not in P. Until you can characterize what mean by the size of a subroutine in this context, the password cracker example is simply meaningless wrt P ?= NP.

Finally, to the more abstract question... here there is a definite, simple answer:

should there be a problem whose solution is in NP but not in P but not NP-complete would this imply that P != NP?

If there is a problem whose solution is in NP but not P, then it follows that there does not exist any NP-complete problem in P.

Why? Proof by contradiction: An NP-complete problem in P can encode and solve every NP problem in polynomial time. Since there (in your hypothesis) exists an NP problem not in P, then there does not exist a P solution to any NP-complete problem.

You asked a cs faculty member about this? Sheesh.

Ah. I see this is a running gag, so to speak. :-)

http://lambda-the-ultimate.org/node/4610

Thanks for the reply. I wasn't sure about that and I am still not sure how to formulate the problem entirely in TM form. It would seem to me that any subroutine would be similar to writing two strings on a tape and comparing them which in TM terms requires several traversals of the string but is still in P time. The size of the subroutine if one views it in terms of a UTM including the the tape space to hold the comparator string should be some constant size + the extra tape space so it would still be the case unless I am incorrect.

maybe gig rather than gag :P. I am actually curious why something in the realm of normal algorithms like password crackers are related to theory and why it's impossible to show for sure perhaps that the algorithm not in P.

Actually that's something I am unsure about. Is it possible to formulate imperfect knowledge situations in complexity theory? This is quite common in practice since with OS protections your programs don't have access to all the information available to the kernel part of the system.