Discussion Overview
The discussion centers around the complexity of the SUBSET-SUM problem, specifically whether it can be solved in polynomial time when the target value is represented in unary. Participants explore the implications of unary representation on algorithm efficiency and complexity classes.
Discussion Character
- Debate/contested
- Technical explanation
- Mathematical reasoning
Main Points Raised
- One participant questions the possibility of solving the SUBSET-SUM problem in polynomial time with a unary target, suggesting that the problem involves finding a subset of numbers that sums to the target.
- Another participant expresses skepticism, stating that unary representation does not change the NP-hard nature of the knapsack problem.
- A different viewpoint highlights that a dynamic programming approach can solve the subset-sum problem in O(nt) time, arguing that if the target is unary, the running time becomes polynomial in relation to the input size.
- Another participant elaborates that any exponential time problem can be reduced to polynomial time with unary input representation, noting that the conversion from unary back to binary is polynomial in the size of the unary input.
- It is mentioned that the representation of input can significantly affect the runtime of various problems, with examples from graph theory regarding adjacency list versus adjacency matrix representations.
Areas of Agreement / Disagreement
Participants express differing views on the impact of unary representation on the complexity of the SUBSET-SUM problem. There is no consensus on whether it can be solved in polynomial time, as some argue for its feasibility while others maintain that it remains NP-hard.
Contextual Notes
The discussion does not resolve the implications of unary representation on the complexity class of the SUBSET-SUM problem, and assumptions regarding input size and representation are not fully explored.