Timeline for Why not to take the unary representation of numbers in numeric algorithms?
Current License: CC BY-SA 4.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Nov 18, 2019 at 2:50 | history | suggested | Dracula | CC BY-SA 4.0 | fixed typo and grammer |
| Nov 17, 2019 at 15:43 | review | Suggested edits | |||
| S Nov 18, 2019 at 2:50 | |||||
| Jan 13, 2016 at 23:46 | comment | added | Nikos M. | its ok i did not suggest to change it, rather the 2 comments on drupalist recast the whole question with respect to given machines for a problem | |
| Jan 13, 2016 at 23:43 | comment | added | D.W.♦ | @NikosM., OK, got it. Thanks for the feedback. Personally, I don't believe that statement is incorrect, so I'm going to leave it as is. (My reasoning: The length of the input does depend on the choice of representation, so I don't believe it contradicts anything you wrote.) However it's entirely possible my perspective might be too narrow, or that a more detailed explanation or explanation from a different perspective might add value. Feel free to write an additional answer or suggest an edit if you feel this point could be clearer. | |
| Jan 13, 2016 at 23:35 | comment | added | Nikos M. | i was refering to the final phrase "..polynomial of the length of the input, in bits" and tried to explain why | |
| Jan 13, 2016 at 23:32 | comment | added | D.W.♦ | @NikosM., thanks for your comments and for your attempts to help explain this to Drupalist. One small comment: When you say "the last part is not correct", I'm not sure which part of my answer you think is incorrect. | |
| Jan 13, 2016 at 23:00 | comment | added | Nikos M. | @Drupalist, in the above sense, one representation is a natural candidate (w.r.t the machine of interest), while the other is not This is a more general issue in that a computationaly-hard problem is not an absolute concept but rather a relative one (relative to a specific machine / computational model and representation) | |
| Jan 13, 2016 at 22:55 | comment | added | Nikos M. | @Drupalist, let me offer a short clarification if that helps. length vs value is not necesarily a distinction between polynomial and pseudo-polynomial simply because under a specific representation (e.g unary) both can be equal (so what is the difference?). Rather it can become a difference under a fixed chosen representation, which is chosen by other reasons (e.g less stiorage space in a given machine). In this sense there is a point to distinguish between one representation and the other, because we are only interested in one of them, and it differs from the other. | |
| Jan 13, 2016 at 22:48 | comment | added | Nikos M. | nice, but the last part is not correct. computational complexity does not assume a specific representation (whether one would like to call this bits or triads or whatever). However it indeed does depend on choice of representation (this is in a sense reflected in the relativisation-based proofs which can derive any result i.e both $P=NP$ and $P <> NP$) There is no definition of computational complexity that is only based on bits, in other words | |
| Jan 8, 2016 at 0:22 | comment | added | D.W.♦ | @Drupalist, I'm not entirely sure what you mean by setting $x=n$, so I'm not sure how to answer. At this point I would suggest it might be best to ask a new (self-contained) question (and define all your variables in that question). This platform isn't so good for follow-up questions or back-and-forths: the best way we have to handle it is to ask a new question, based on what you've learned from the answers to this question. | |
| Jan 7, 2016 at 23:17 | comment | added | M a m a D | Thank you very much, from what I understand the difference between the input size and its magnitude is the reason of distinction between polynomial and pseudo-polynomial, by using unary representation I tried to eliminate this difference, If we forget knapsack and back to the numeric algorithms, I would like to know by setting $x=n$ what will be the interpretation of polynomial and pseudo-polynomial? Thanks again | |
| Jan 7, 2016 at 22:59 | vote | accept | M a m a D | ||
| Jan 6, 2016 at 21:20 | comment | added | D.W.♦ | @Drupalist, I've edited my answer to add two paragraphs at the end to answer that question. | |
| Jan 6, 2016 at 21:20 | history | edited | D.W.♦ | CC BY-SA 3.0 | added 555 characters in body |
| Jan 6, 2016 at 20:21 | comment | added | M a m a D | Thank you very much, I didn't know that the complexity class of unary and non-unary of the same algorithm may be different. Why the dynamic programming solution of standard knapsack can not be applied to unary knapsack, and it leaded to different class of complexity? I am having problem with understanding the unary version of problems. | |
| Jan 6, 2016 at 19:48 | history | answered | D.W.♦ | CC BY-SA 3.0 |