Dragonfall
- 1,023
- 5
The subset sum problem is NP complete. What if we replace summing with multiplying? Would it still be np complete?
The Subset Multiply Problem: Is it NP Complete?
- Context: Graduate
- Thread starter Dragonfall
- Start date
-
- Tags
- Complete
Join the discussion
Registration is free. Ask a follow-up in this thread, or start your own.
2 replies · 3K views
Discussion
Mathematics news on Phys.org
Science Advisor
Homework Helper
- 2,832
- 0
Yes, else the subset sum problem wouldn't be NP-hard (take logs).
Dragonfall
- 1,023
- 5
Good point.
Last edited:
Similar threads
NP-Complete Problems to Reading and Understanding
- mathmari
- · Replies 4 ·
- General Math
- Replies
- 4
Protein Folding and NP-Completeness
- cobalt124
- · Replies 5 ·
- Programming and Computer Science
- Replies
- 5
Graduate Relationship between NP-complete and BQP problems
- Dragonfall
- · Replies 1 ·
- General Math
- Replies
- 1
Is HSC NP-Complete in Graph Theory?
- mathmari
- · Replies 1 ·
- Set Theory, Logic, Probability, Statistics
- Replies
- 1
Is the Subgraph Isomorphism problem NP-complete?
- evinda
- · Replies 1 ·
- Programming and Computer Science
- Replies
- 1
Graduate Is NP-Complete Harder to Solve than NP-Hard?
- jetoso
- · Replies 3 ·
- General Math
- Replies
- 3
Ice Cream : NP-complete problem
- mathmari
- · Replies 6 ·
- Set Theory, Logic, Probability, Statistics
- Replies
- 6
Solving Decision Problem with k Colors - NP-Complete
- evinda
- · Replies 6 ·
- Programming and Computer Science
- Replies
- 6
The knapsack problem is NP-complete
- mathmari
- · Replies 14 ·
- Programming and Computer Science
- Replies
- 14
Graduate Solving the NP-Completeness of Travelling Salesman Problem
- Dragonfall
- · Replies 3 ·
- General Math
- Replies
- 3