4 ms·

I think you're proving my point here -- finding the optimal solution for a Rubik's cube is probably at least PSPACE-Hard, which is probably exponential. So com

I think you're proving my point here -- finding the optimal solution for a Rubik's cube is probably at least PSPACE-Hard, which is probably exponential. So complexity theory is confirming your intuition, which is that 'optimization type problems' are hard.

dom0 10y ago
Even the basic rucksack optimization problem is NP-hard. I'd dare say that a huge class of optimization problems maps very naturally to this particular one, https://news.ycombinator.com/item?id=13316776 https://news.ycombinator.com/item?id=13316776 for starters.
- taeric 10y ago
  Ok, so optimization problems are potentially bounded with smaller coefficients than we would think. What about sequencing life? Supposedly we share a lot at the genomic level with animals we are vastly different from. Could a large degree of the polynomial that is life explain that divergence?
  - dom0 10y ago
    What?
    - taeric 10y ago
      Ha! I'm just trying to get a better feel for what is being said. Definitely the dumbest person in this particular conversation. I am assuming you are pushing the same angle as the other poster. That is, most optimization problems are actually not "large constants" in the exponents. So, since most of what developers think of as "hard" are almost all classical NP problems, maybe it makes sense to look at other things we don't typically think of as computational. Could just be nonsensical, though. I fully accept that.
taeric 10y ago
I misunderstood your point, then. I thought you were saying that we rarely see giant exponents in things. My question is if we typically do see giant exponents, but make do with much simpler solutions. (That make sense?)
- smallnamespace 10y ago
  I am saying we rarely see giant exponents (on polynomial-time algorithms) in practice, because most algorithms that we intuitively think of as 'hard' turn out to be in NP or PSPACE or other complexity classes that we have decent reason to suspect have a lower-bound exponential running time.
  - taeric 10y ago
    Sadly, I'm not sure I understand the point. Aren't we saying these could be exponential, just with large coefficients? Edit: I meant "small" coefficients above. Apologies.
    - smallnamespace 10y ago
      P: O(n^k), where large k makes it 'slow' but still polynomial NP: probably O(e^kn), k>1, where k close to 1 makes it 'fast', but still exponential The objection is that k can be big for some polynomial algorithms but small (near 1) for other exponential ones, so we can have 'slow' polynomial algorithms and 'fast' exponential ones. But in practice, k is usually small for polynomial algorithms and not close to 1 for exponential ones so simply knowing whether an algorithm is exponential or polynomial tells you something. The 'hard' problems you gave me all (probably) fall into the exponential runtime class, whereas the easier ones (like finding any solution to a Rubiks) fall into the polynomial runtime. So your intuition of 'hard' vs. 'easy' matches complexity theory's evaluation, even though theoretically there could be really slow 'easy' problems and really fast 'hard' ones.

dom0 10y ago

Even the basic rucksack optimization problem is NP-hard. I'd dare say that a huge class of optimization problems maps very naturally to this particular one, https://news.ycombinator.com/item?id=13316776 https://news.ycombinator.com/item?id=13316776 for starters.

taeric 10y ago
Ok, so optimization problems are potentially bounded with smaller coefficients than we would think. What about sequencing life? Supposedly we share a lot at the genomic level with animals we are vastly different from. Could a large degree of the polynomial that is life explain that divergence?
- dom0 10y ago
  What?
  - taeric 10y ago
    Ha! I'm just trying to get a better feel for what is being said. Definitely the dumbest person in this particular conversation. I am assuming you are pushing the same angle as the other poster. That is, most optimization problems are actually not "large constants" in the exponents. So, since most of what developers think of as "hard" are almost all classical NP problems, maybe it makes sense to look at other things we don't typically think of as computational. Could just be nonsensical, though. I fully accept that.

taeric 10y ago

I misunderstood your point, then. I thought you were saying that we rarely see giant exponents in things. My question is if we typically do see giant exponents, but make do with much simpler solutions. (That make sense?)

smallnamespace 10y ago
I am saying we rarely see giant exponents (on polynomial-time algorithms) in practice, because most algorithms that we intuitively think of as 'hard' turn out to be in NP or PSPACE or other complexity classes that we have decent reason to suspect have a lower-bound exponential running time.
- taeric 10y ago
  Sadly, I'm not sure I understand the point. Aren't we saying these could be exponential, just with large coefficients? Edit: I meant "small" coefficients above. Apologies.
  - smallnamespace 10y ago
    P: O(n^k), where large k makes it 'slow' but still polynomial NP: probably O(e^kn), k>1, where k close to 1 makes it 'fast', but still exponential The objection is that k can be big for some polynomial algorithms but small (near 1) for other exponential ones, so we can have 'slow' polynomial algorithms and 'fast' exponential ones. But in practice, k is usually small for polynomial algorithms and not close to 1 for exponential ones so simply knowing whether an algorithm is exponential or polynomial tells you something. The 'hard' problems you gave me all (probably) fall into the exponential runtime class, whereas the easier ones (like finding any solution to a Rubiks) fall into the polynomial runtime. So your intuition of 'hard' vs. 'easy' matches complexity theory's evaluation, even though theoretically there could be really slow 'easy' problems and really fast 'hard' ones.