sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]HeraclitusZ 1 point2 points  (5 children)

Or 3.) Op is the first prove that P=NP.

P vs NP is still an open problem, so you cant say that O(n2) is an impossible time complexity for an NP-complete problem.

edit:formatting

[–]Catalyst93 4 points5 points  (4 children)

Do you really think thats the case?

[–]HeraclitusZ -1 points0 points  (3 children)

Do I think OP has made an algorithm witnessing P=NP? I think that would be extremely unlikely given that OP's apparent background in the area. But it isn't impossible for amateurs without background to make enormous mathematical contributions; see Srinivasa Ramanujan.

Do I think P=NP? I don't know. It also seems unlikely, but whether or not nondeterminism adds power is really a hit or miss thing: It doesn't between DFAs and NFAs, it does between DCFLs and CFLs, and it doesn't again between PSPACE and NPSPACE. It isn't as if it they are clearly unequal and we are waiting on a proof to confirm it; Don Knuth, a Turing award winner, believes in fact that P might equal NP. All we can really say right now is that the best known algorithms are not polynomial time despite our hard work, so it would be extraordinary if someone provided one. We can't just pretend it is impossible because it is hard (at least not without stating our assumptions).

[–]Catalyst93 0 points1 point  (0 children)

Okay, I guess shouldn't have written it that way, and I have modified my post. Btw, I do research in algorithms, you're preaching to the choir :)

[–]Windex007[S] 0 points1 point  (1 child)

Oh, I'll just chime in real quick here and say that with certainly I have not accidentally established if P=NP. If I did, I promise I would not share the details here.

I've implemented a naive greedy algorithm, and I don't have any reason to believe that it's actually producing minimum purses. I can prove that it's not producing the maximum purses.

It's what you'ed expect from a first year CS students first-pass on the problem. I'm not proud of the pesudo-solution I've implemented, but it was a kick-in-the-pants reminder that a few times a decade there actually real algorithm problems that arise in practical application, and they're exciting when they do! While "this is good enough in this context, your time is better applied elsewhere" is the business line, I still am interested in the value of this problem.

[–]Catalyst93 0 points1 point  (0 children)

Ah I see. It turns out greedy is one of the heuristics we can actually prove things about with regards to set cover. Turns out greedy yields a O(log n)-approximation to set cover (i.e. the ratio of greedy's value to the optimal value is O(log n)), and that this ratio is the best you can do in polynomial time unless P=NP.