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. Start your own thread to ask a follow-up.
2 replies · 3K views
Mathematics news on Phys.org
Discussion
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
Graduate Can NP-complete problems reduce to each other?
- David Carroll
- · Replies 4 ·
- General Math
- Replies
- 4
NP-Complete Problems to Reading and Understanding
- mathmari
- · Replies 4 ·
- General Math
- Replies
- 4
What makes a decision problem NP-complete?
- 2sin54
- · Replies 10 ·
- Programming and Computer Science
- Replies
- 10
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
Solving Decision Problem with k Colors - NP-Complete
- evinda
- · Replies 6 ·
- Programming and Computer Science
- Replies
- 6
Proving longest path is NP-complete by reduction from Hamiltonian path
- evinda
- · Replies 19 ·
- Programming and Computer Science
- Replies
- 19