> Despite having done my undergrad in CS, I never understood what NP-hard really meant
Not having done CS undergrad, I have never really understood even P/NP. The naive explanation of problems that are easy to solve and check vs problems that are difficult to solve but easy to check seems to leave something essential out.
I mean, with the naive explanation you are I think you are left with either of two options:
1. A philosophical issue of not being able to prove a negative, you really can't prove that there is not a way to solve a problem fast.
2. That obviously P!=NP. You just for example lose information before giving the problem to the solver, say, I'm thinking a float with n decimals, then I round it to nearest integer and ask you to find the float given the integer. I can check the guess in linear time as n increases, but your difficulty increases exponentially as n increases.
I am pretty sure there is something in this problem that makes it a not legal P/NP problem, but I have no idea what. I have a couple of times tried to look for more formal definitions of P/NP, but the jargon goes immediately above my head.
(The "guess" is admittably there a bit informal, if you want a bit more formal problem, you take a process C that is mathematically proven to be sufficiently sensitive to initial conditions (e.g. chaotic), take integer x and calculate y = C(x), round y and ask what's x.)
Not having done CS undergrad, I have never really understood even P/NP. The naive explanation of problems that are easy to solve and check vs problems that are difficult to solve but easy to check seems to leave something essential out.
I mean, with the naive explanation you are I think you are left with either of two options:
1. A philosophical issue of not being able to prove a negative, you really can't prove that there is not a way to solve a problem fast.
2. That obviously P!=NP. You just for example lose information before giving the problem to the solver, say, I'm thinking a float with n decimals, then I round it to nearest integer and ask you to find the float given the integer. I can check the guess in linear time as n increases, but your difficulty increases exponentially as n increases.
I am pretty sure there is something in this problem that makes it a not legal P/NP problem, but I have no idea what. I have a couple of times tried to look for more formal definitions of P/NP, but the jargon goes immediately above my head.
(The "guess" is admittably there a bit informal, if you want a bit more formal problem, you take a process C that is mathematically proven to be sufficiently sensitive to initial conditions (e.g. chaotic), take integer x and calculate y = C(x), round y and ask what's x.)