Questions tagged [np-complete]

For questions about algorithms for so-called 'NP complete' problems, which are among the hardest computational problems to solve.

Filter by
Sorted by
Tagged with
-4 votes
1 answer
132 views

How to determine computational infeasibility of NP Complete

For an NP complete problem, how is computational infeasibility determined? Are there guidelines that that determine whether an NP Complete problem is computationally infeasible?
user avatar
1 vote
2 answers
99 views

Algorithm. Find the group of documents with the least amount of words

I need help with a problem which I have been working for the last month. I have a group of documents, each document has a set of unique words (if the word appears more than once in the document, I ...
user avatar
  • 119
0 votes
2 answers
121 views

How to wait for a certain amount of time if time functions are not reliable [closed]

How can I manage my code to exactly wait for a certain amount of time (say 10s), if all * time functions on the system are not reliable and return immediately ? Sleep(10000); // Do not sleep for 10s ...
user avatar
  • 23
0 votes
1 answer
160 views

Split k sets to 2 groups of sets

Given k sets ,each contain several elements . I want to split them to two groups , the first group contains m sets ,the second group contain n sets , m + n = k . Let w1 be the sum of the weights of ...
user avatar
  • 121
59 votes
4 answers
81k views

Trying to understand P vs NP vs NP Complete vs NP Hard

I am trying to understand these classifications and why they exist. Is my understanding right? If not, what? P is polynomial complexity, or O(nk) for some non-negative real number k, such as O(1), O(...
user avatar
  • 701
0 votes
2 answers
497 views

Optimization problem where to start, what algorithms to use? [closed]

I have an optimization problem and I was wondering where to start from to be able resolve it. I think it can be solved with an NP-complete algorithm but I am not sure where to start from. The problem ...
user avatar
  • 135
3 votes
2 answers
536 views

Algorithm to find minimal set

I have a set of sets S and I want to find a minimal set of elements M such that each set in S shares at least one element with M. S = set of sets ∀ f∈S ∃e · e∈f ∧ e∈M For example: S = {{1}, {1, 2, ...
user avatar
  • 481
2 votes
2 answers
689 views

Dynamic Programming Problem - To find smallest integer number 'x' which contains only digits 1's and 0's such that x mod n = 0

To design an algorithm that will output the smallest integer number 'x' which contains only digits 1's and 0's such that x mod n = 0 and x > 0..... For example: 2 divides 10 3 divides 111 4 ...
user avatar
3 votes
2 answers
1k views

Simplified knapsack in PHP

I have two instances where I'd like to display information in a "justified" alignment - but I don't care if the values are switched in order. One example being displaying the usernames of people ...
user avatar
  • 367