Questions on the topic of NP-Completeness, which comes from Theoretical Computer Science
Questions tagged [np-complete]
676 questions
-1
votes
1 answer
Does graph G contain a 100-node clique as a subgraph? Is it in P?
Although the clique problem is NP-complete, is this restricted version also considered to be NP-complete or is it actually in P?
I would imagine since you are still trying to solve the clique problem then this problem would still be NP-complete but…
sanic
- 447
-1
votes
1 answer
Question about NP with certificate
all.
I have some question about proving NP-complete
The conditions of proving problem is NP-complete is following.
1) Problem is in NP
2) Problem is reducible other from NP-Complete Problem (Ex. SAT)
To do condition #1, we use certificate.
My…
Tony_SSU
- 21
-2
votes
1 answer
Finding a reduction for two-Subset sum problem
I'd like to prove that the following problem is NP-complete. I'd just like to know what reduction I should do:
Two Subset Sum: Given a set S of integers and an integer T, determine whether there are two subsets of S such that the sum of the numbers…
BAM
- 433
- 1
- 7
- 17