Skip to main content
Computer Science

Return to Question

added 12 characters in body; edited tags; edited title
Source Link
user2566092
user2566092
  • 1.7k
  • 10
  • 17

Is finding the smallest subsetcollection of stringssubsets so that the number of distinct characterselements among the stringssubsets is <= the number of stringssubsets NP-hard?

Given a setcollection of non-empty strings over an alphabet that issubsets of $\{1,2,\ldots,N\}$ ($N$ not fixed), the problem is to find the smallest non-empty subsetcollection of stringssubsets so that the number of distinct characterselements appearing among the union of stringssubsets is less than or equal to the number of stringssubsets chosen. This seems like an NP-hard problem but I can't prove it. Any help?

Is finding the smallest subset of strings so that the number of distinct characters among the strings is <= the number of strings NP-hard?

Given a set of non-empty strings over an alphabet that is not fixed, the problem is to find the smallest non-empty subset of strings so that the number of distinct characters appearing among the union of strings is less than or equal to the number of strings chosen. This seems like an NP-hard problem but I can't prove it. Any help?

Is finding the smallest collection of subsets so that the number of elements among the subsets is <= the number of subsets NP-hard?

Given a collection of non-empty subsets of $\{1,2,\ldots,N\}$ ($N$ not fixed), the problem is to find the smallest non-empty collection of subsets so that the number of distinct elements appearing among the union of subsets is less than or equal to the number of subsets chosen. This seems like an NP-hard problem but I can't prove it. Any help?

Tweeted twitter.com/#!/StackCompSci/status/503357690723459072
added 20 characters in body
Source Link
user2566092
user2566092
  • 1.7k
  • 10
  • 17

Given a set of non-empty strings over an alphabet that is not fixed, the problem is to find the smallest non-empty subset of strings so that the number of distinct characters appearing among the union of strings is less than or equal to the number of strings chosen. This seems like an NP-hard problem but I can't prove it. Any help?

Given a set of strings over an alphabet that is not fixed, the problem is to find the smallest subset of strings so that the number of distinct characters appearing among the union of strings is less than or equal to the number of strings chosen. This seems like an NP-hard problem but I can't prove it. Any help?

Given a set of non-empty strings over an alphabet that is not fixed, the problem is to find the smallest non-empty subset of strings so that the number of distinct characters appearing among the union of strings is less than or equal to the number of strings chosen. This seems like an NP-hard problem but I can't prove it. Any help?

Source Link
user2566092
user2566092
  • 1.7k
  • 10
  • 17

Is finding the smallest subset of strings so that the number of distinct characters among the strings is <= the number of strings NP-hard?

Given a set of strings over an alphabet that is not fixed, the problem is to find the smallest subset of strings so that the number of distinct characters appearing among the union of strings is less than or equal to the number of strings chosen. This seems like an NP-hard problem but I can't prove it. Any help?