Does P = NP?

Depends if it's in a sealed box that you can't see into.

I don't know.

An open question to Jon`C:

Does freelancer suck?

I want my own thread too =[

If P = 0.5P and N = 2P, then, yes.

At what?

Making threads.

Trying to be intellectual.

Yes.

Yes.

Is there a punchline I'm missing here?

Fun fact: the P?NP problem is the reason our currency comes in 0.01,0.05,0.10,0.25,1,5,10,20,100 denominations. We can use a polynomial-time greedy algorithm to count change, starting from the highest denomination to the lowest, and we get the smallest number of coins needed to form that change (exercise to prove.)

What happens if we choose arbitrary denominations?

e.g. if you have the denominations 0.01,0.20,0.21, make 0.60 in change.

Using the greedy algorithm, you take 2(0.21)+18(0.01), or 20 coins.
But the correct solution is clearly to take 3(0.20), or 3 coins, so the greedy algorithm is no longer sufficient to find an optimal solution.

When you allow arbitrary denominations, the problem becomes NP-complete. The greedy approach is linear in the number of denominations, but this problem is linear in the value of the amount of change that must be made. The value of a number, however, is in Theta(b^n) where b is the radix and n is the number of places. So the problem is exponential in the size of the input.

So here's the challenge for all of you: if you can find a way to quickly count change in an arbitrary money system, using the least number of coins, you have proven that P=NP.

You left out the part about winning 1,000,000$

Jon'c out of curiosity, what is your IQ? I'm not being a smartass either, your just God damned gifted.

IQ isn't really relative to actual intelligence. Mine is 136 and I'm almost always borderline retarded.

I got 202 on an IQ test once by pure random guessing. I should have screenshotted that.

Cool Matty, online IQ tests don't count.

Well I sure hope not, after all, I got a 202 for guessing.

Supposedly Richard Feynman had an IQ of 120. Antony is not smarter than Richard Feynman.

Hey guys, doesn't matter what you have, it's what you do with it.

120 barely counts as smart.

But how are you defining "quickly"? Developing an alogorithm to give you the correct answer isn't difficult.

motion of the ocean, blah blah

Polynomial time. And yes. Actually, it is _very_ difficult. We aren't talking about verifying that an answer is correct, and we aren't talking about heuristics that produce decent-but-suboptimal results. And we certainly aren't talking about braindead brute force algorithms that run in superpolynomial time. We are talking about producing the optimum solution for all inputs in polynomial time.

Jon: I was under the impression that solving one NP-complete problem wasn't proof that P = NP. Is it?

If you can find one polynomial-time algorithm for an NP-complete problem, you have proven that P=NP.

I was really hoping for Freelancer to ask something that only Jon`C could answer. Rather than something which everyone who has ever written an algorithm should know about.

You should have known better.

Man, P versus NP, something I haven't given any real thought to since sophomore year of college.

thats about where that statement stops for me.

Are you being sarcastic, or are you really not interested in the theory of computation?

I'll ask one then!

Can you tell us what plans the Goa'uld have in store for us, so that we may prepare for a plan of our own to foil them?

Obviously I don't expect him to have the solution, but I was curious how he'd answer. I expected him to say no or at least 'probably not.'

There have been just as many false proofs for P=NP as there have been for P≠NP. Intuitively I don't see how they can possibly be equal, but the only correct answer to the question is "I don't know."

I think the real question is, would a computer answer "I don't know"?

I don't like IQ tests, because I consider them unreliable when it comes to consistency. I've done a couple of IQ tests (standardized and supervised ones, not online, though keep in mind that Finnish tests are a lot easier since Finns are generally less intelligent, which is mostly attributed to hereditary factors...the average Finn would be mildly retarded by American standards, for example) with considerably different results, because the first time I was so drugged up that it affected my cognitive skills.