338 questions
1
vote
1
answer
117
views
Why does Algorithms Illuminated use Turing reductions instead of Karp for NP-hardness
The book Algorithms Illuminated Part 4 has the following definition to prove problems NP-hard:
A problem A reduces to another problem B if an algorithm that solves B can be easily translated into one ...
- 297
0
votes
0
answers
85
views
Implementation of distributed greedy algorithm for finding maximum independent set
Can anyone share any implementation on how to implement a distributed greedy algorithm for maximum independent set or any implementation of distributed graph algorithm in C++? I checked this one https:...
- 111
1
vote
0
answers
224
views
K-Hamiltonian Path problem and NP-completeness
Consider the K-Hamiltonian Path (KHP) decision problem stated below:
KHP = (G, K), where:
G = (V, E) is an undirected graph of n vertices and m edges
K is a positive integer
Do there exist at least n/...
- 11
2
votes
0
answers
241
views
Distributing marbles into buckets for maximal colour sharing
i've got a problem that feels very much like it's NP-hard but I would love some help proving it primarily.
Secondary to that, if an optimal polynomal time algorithm can be proposed that is even better,...
- 530
0
votes
0
answers
31
views
Get all subsets of fairly large set of elements, {1,2,3,...,254,255}, that sum up to a value 666
While there are many answers to this sort of question, many of them do not handle large sets or sums well. I want to get all subsets of set {1,2,3,...,254,255} that sum up to a value 666, and ...
- 328
-2
votes
1
answer
470
views
3 partition np completeness
I want to know how 3 partition problem is NP complete ? We have to find triplets in set which sums to target. So isn't time complexity will be O(n^3) which is polynomial ?
solution: https://www....
- 23
0
votes
0
answers
112
views
P=NP in Exponential Space?
Suppose that we find that, for any NP-complete problem, there is an algorithm that can solve it in P time. However, the algorithm takes exponential space. For example, the algorithm to revert SHA256 ...
- 11
0
votes
1
answer
31
views
Best practice to search for a list of subset holders that holds a subset of a complete set?
What is the best practice to search a list of stores that holds a subset of goods of a library of goods?
Here is the scenario:
a library of goods has (0 to totalAmountofGoods), each store can hold a ...
- 25
1
vote
0
answers
139
views
Judge:Some N P -complete problems have polynomial time algorithms, but some others do not
Here is the context of the question:
For each of the following statements, indicate whether it is true, false, or unknown, where 'unknown' indicates that scientists have not conclusively determined ...
- 21
0
votes
1
answer
584
views
Independent Set with dist(u, w) > 2
I need helping solving a reduction problem:
Given a Graph G and a number k, Is there a set V' in V(G) such that |V'| >= k and the dist(u,v) > 2 for all u, v in V'?
Now at first glance this looks ...
- 69
-1
votes
1
answer
109
views
proof of SAT np completeness
I know if we want to prove the np completeness of some problem we must show these :
there is a nondeterministic polynomial solution for the problem
all other np problems are reducible to the problem
...
0
votes
0
answers
100
views
What problem type the Power Set belong to?
I don't seem to find any much resource about "Power Set" problem.
Is Power Set a NP-Complete or NP-Hard problem? And why? Can someone advise me?
- 3,191
1
vote
1
answer
151
views
Are these two definitions of an NP-Complete problem equivalent?
Definition 1 (usual definition)
A problem B is NP-Complete if
B is in NP
For C in NP, C is polynomal-time reducible to B
Definition 2 (in a few documents)
A problem B is NP-Complete if
B is in NP
...
- 11
0
votes
0
answers
42
views
What would be considered the number of elements in a boolean satisfiability problem?
Another way to put this question is, if a boolean satisfiability solution had an efficiency of O(2^n), what would be considered n?
It seems like it could be the number of variables in the expression, ...
- 1
0
votes
1
answer
457
views
Is it NP-complete to find a sub-maximal clique which is at least max clique size - 1?
It is well-known that it is a NP-complete problem to find a maximal clique in a graph. But I wonder know if it possible to find a sub-maximal clique in a graph in polynomial time. That is, given that ...
- 153