Timeline for Is unconstrained integer convex optimization problem NP-hard?
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 16, 2013 at 14:36 | history | edited | user9072 |
tags
|
|
| Nov 16, 2012 at 23:16 | history | edited | Vahan | CC BY-SA 3.0 |
added 524 characters in body
|
| Nov 16, 2012 at 18:28 | comment | added | Emil Jeřábek | The question needs to be rewritten so that it unambiguously defines the computational model being used and what is meant by “NP-hard” in this context, in sufficient detail so that it becomes a well-defined problem, rather than a vague metaphor. Until then I’m voting to close as not a real question. | |
| Nov 16, 2012 at 17:43 | comment | added | Joel David Hamkins | How can $F$ be fixed, if $N$ is varying, if the domain of $F$ is supposed to be $\mathbb{Z}^N$? | |
| Nov 16, 2012 at 16:44 | comment | added | Vahan | oops, the only input is N | |
| Nov 16, 2012 at 16:34 | history | edited | Dima Pasechnik | CC BY-SA 3.0 |
added 15 characters in body
|
| Nov 16, 2012 at 16:33 | comment | added | Emil Jeřábek | This is making less and less sense. NP is a class of unrelativized problems, it is meaningless to compare it with problems depending on an oracle. Even worse, if the function is provided by an oracle, then the problem has no input at all! In such a setting, no concepts involving complexity measures based on the length of the input (such as polynomial-time reductions, NP, etc) make any sense. | |
| Nov 16, 2012 at 15:54 | comment | added | Vahan | F:Z^N -> R and assume there is a oracle giving the value of F(x) for each integral x. | |
| Nov 16, 2012 at 15:52 | comment | added | Emil Jeřábek | First, a function from where to where? Second, the input of a computational problem is a finite string in a finite alphabet. How do you represent your function in such a way? | |
| Nov 16, 2012 at 15:44 | comment | added | Vahan | F is an arbitrary convex function, doesn't have to be smooth. I guess the only input is F, but I'm interested in a general result for any convex F. | |
| Nov 16, 2012 at 15:43 | answer | added | Igor Rivin | timeline score: 2 | |
| Nov 16, 2012 at 15:40 | comment | added | Emil Jeřábek | What is the input of the problem, and what is $F$? | |
| Nov 16, 2012 at 15:18 | history | asked | Vahan | CC BY-SA 3.0 |