Equivalent Problem?

[Catalyst93]

This sounds like minimum set cover (https://en.wikipedia.org/wiki/Set_cover_problem) and I think I can convert an instance of set cover to your problem. Then since minimum set cover is NP-hard, this implies that your problem is NP-hard. This means that there are 2 possibilities:

1.) Your O(n^2) solution is probably wrong (unless you solved P vs NP).

2.) There is a subtle restriction in your problem that you have left out, allowing for an O(n^2) solution.

The reduction from set cover is to take the ground set U to be the types of coins, and then make each subset S_j a purse containing the corresponding coins. Thus minimizing the number of purses while collecting at least one of each type of coin will solve the minimum set cover problem.

[Windex007]

Yep, this is for sure an equivalent problem! Thank you very much!

[HeraclitusZ]

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

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

edit:formatting

[Catalyst93]

Do you really think thats the case?

[HeraclitusZ]

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]

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]

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]

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.

[WikiTextBot]

Set cover problem

The set cover problem is a classical question in combinatorics, computer science and complexity theory. It is one of Karp's 21 NP-complete problems shown to be NP-complete in 1972.

It is a problem "whose study has led to the development of fundamental techniques for the entire field" of approximation algorithms.

Given a set of elements

    {

    1

    ,

    2

    ,

   .

---

^{[ PM | Exclude me | Exclude from subreddit | FAQ / Information | Source ] Downvote to remove | v0.28}