5 ms·

Too late, no take backs. P now equals NP and we must live with the consequences!

ineedasername 5y ago
So much for chess. Instead of memorizing countless games, expert players will all just memorize the algorithm, and winning will come down to a coin flip of who goes first.
- jcranmer 5y ago
  Chess is EXPTIME, not NP. Unless you want to consider that it's only played on a fixed-size board, in which case it's actually a constant-time algorithm.
  - ineedasername 5y ago
    Ah, thanks. I like being wrong on HN because I learn things. What's most interesting to me is why I was wrong, so I'll share: I was thinking in terms of infinite moves when I should have been thinking in terms of non-infinite board states: A move, though possibly part of an infinite series of moves, is still only one of a finite number of states for the board. And each state can theoretically be evaluated to results in a win/lose/draw for either white/black assuming both player play a perfect game. Now I'm going to go way outside my comfort zone with the hope of correction or confirmation: Since the nature of chess on a board of of N dimensions is EXPTIME-hard, would chess on an infinite board be NEXPTIME-hard? (And if not, what level of the time hierarchy would that fall under?)
    - PeterisP 5y ago
      Chess also has a finite number of moves (at least on a finite board), the 50-move rule and the 3-repetition rule ensure that a game can't last infinitely even if both players want to and ends in a forced draw.
      - agalunar 5y ago
        It's actually because of the 5-fold repetition and 75-move rules! The game is not necessarily over at 3 and 50 – you merely have the right to claim a draw.
      - ineedasername 5y ago
        Both of those require a player to claim the draw. There is no reason within the rules of the game for why it could not be infinite in the # of moves. The rule has also at times been restricted only to tournament play. Also, if chess was "solved" and board states determined "winnable" after significantly more moves, the rules might very well change to extend that limit. Something along those lines has happened before: When a combination of pieces have been shown to be "winnable" but might exceed the 50 move rule, exceptions have been made to the rule to allow more time to develop the win. At some point though, the rules went back to 50, but still with conditions about pawn moves, pieces taken, etc. The history is interesting: 50 was originally chosen (or maybe just compromised on) because players felt than all winnable games could be won in 50 moves or under.
        pentestercrab 5y ago
        The fivefold repetition rule requires no claim by the players.
        ineedasername 5y ago
        Ah, true... Given the double criteria for that (lack of pawn movement) it extends things a bit, but there would still be a finite number of moves. However on an info it's chess board there would always be a unique board state possible. That doesn't by any means refute your point, only add a twist to things.
    - elliekelly 5y ago
      Thanks for explaining this, I learned something, too!
  - mrfusion 5y ago
    If the universe is finite, does that mean every problem is a constant time algorithm?
    - deleted 5y ago
      [deleted]
    - emerged 5y ago
      We do seem to spend an awful lot of time worrying about infinities when it appears the cosmological horizon is finite. But I guess if we find some way around that we will be prepared.
      - raattgift 5y ago
        In an accelerating expanding universe like the one we appear to occupy (and the one modelled by our current "concordance" standard model of comology), the comoving horizon is at constant comoving distance. Cast into more Earth-centric coordinates, it is at a finite spatial distance at all finite times. However, there is no reason to expect that a timelike worldline rooted at "here and now" (converting a chosen comoving coordinate into the origin of spherical coordinates for a Eulerian observer) cannot be extended into the infinite future, and at +infinite time the horizon will be at an infinite spatial distance in this system of coordinates. We don't even need to say anything about the matter content of the Hubble volume at any time, anything about -infinite time, or anything about how various measures of entropy fit in; all of these can generate infinities that defy easy (and possibly any) removal in a universe similar to the concordance model. A taste of this can be found at https://en.wikipedia.org/wiki/Cosmological_horizon#Future_horizon https://en.wikipedia.org/wiki/Cosmological_horizon#Future_ho... More deeply and technically, Baez's "Struggles with the Continuum" is great A smooth manifold tends to generate infinities and infinitesimals, and all our fundamental physical descriptions of the universe we inhabit are (at least at present) defined on a Lorentzian spacetime, which is a smooth manifold. He discusses practical reasons to [a] worry about infinities and [b] to work with them anywhere because they might not be removable. https://arxiv.org/abs/1609.01421 https://arxiv.org/abs/1609.01421 (§5 starting on p. 27 is directly relevant, and the concluding §6 is pithy).
    - 5y ago
- colejohnson66 5y ago
  That’s already a thing with Tic-Tac-Toe.[0] Granted, Tic-Tac-Toe is exponentially less complicated than Chess. [0]: https://xkcd.com/832/ https://xkcd.com/832/
shadowgovt 5y ago
BRB air gapping every single device I own and setting my internet router on fire. ;)
- munk-a 5y ago
  BRB computing several billion bitcoin hash completions on my Casio.
  - anyfoo 5y ago
    Serious question: Is computing cryptographic hashes, by any measure, actually NP-hard? Computing a single hash seems pretty constant to me. Or is there an alternative way to formulate the problem on a higher level, so that cracking cryptographic hashes is NP-hard?
    - deleted 5y ago
      [deleted]
    - staticassertion 5y ago
      Computing any hash isn't, but finding a preimage is NP.
      - anyfoo 5y ago
        Can you elaborate? Is it because a non-deterministic automaton would find the solution immediately (by trying all hashes at once), but a deterministic one of course wouldn't? I think I want to know in more detail why finding a pre-image is non-deterministically polynomial (though I might have answered that to myself with the sentence before), and more importantly why it's deterministically non-polynomial, and on what. Annoying, I took theoretical computer science in university and used to have a better grasp on this, but apparently that part of complexity theory atrophied by now.
        deleted 5y ago
        [deleted]
meepmorp 5y ago
This is the way.
mikewarot 5y ago
While we're at it... the halting problem CAN be solved, for a computer with N bits of state, in a time proportional to 2^N. It remains unsolvable for Turing machines, however. 8-)

So much for chess. Instead of memorizing countless games, expert players will all just memorize the algorithm, and winning will come down to a coin flip of who goes first.

jcranmer 5y ago
Chess is EXPTIME, not NP. Unless you want to consider that it's only played on a fixed-size board, in which case it's actually a constant-time algorithm.
- ineedasername 5y ago
  Ah, thanks. I like being wrong on HN because I learn things. What's most interesting to me is why I was wrong, so I'll share: I was thinking in terms of infinite moves when I should have been thinking in terms of non-infinite board states: A move, though possibly part of an infinite series of moves, is still only one of a finite number of states for the board. And each state can theoretically be evaluated to results in a win/lose/draw for either white/black assuming both player play a perfect game. Now I'm going to go way outside my comfort zone with the hope of correction or confirmation: Since the nature of chess on a board of of N dimensions is EXPTIME-hard, would chess on an infinite board be NEXPTIME-hard? (And if not, what level of the time hierarchy would that fall under?)
  - PeterisP 5y ago
    Chess also has a finite number of moves (at least on a finite board), the 50-move rule and the 3-repetition rule ensure that a game can't last infinitely even if both players want to and ends in a forced draw.
    - agalunar 5y ago
      It's actually because of the 5-fold repetition and 75-move rules! The game is not necessarily over at 3 and 50 – you merely have the right to claim a draw.
    - ineedasername 5y ago
      Both of those require a player to claim the draw. There is no reason within the rules of the game for why it could not be infinite in the # of moves. The rule has also at times been restricted only to tournament play. Also, if chess was "solved" and board states determined "winnable" after significantly more moves, the rules might very well change to extend that limit. Something along those lines has happened before: When a combination of pieces have been shown to be "winnable" but might exceed the 50 move rule, exceptions have been made to the rule to allow more time to develop the win. At some point though, the rules went back to 50, but still with conditions about pawn moves, pieces taken, etc. The history is interesting: 50 was originally chosen (or maybe just compromised on) because players felt than all winnable games could be won in 50 moves or under.
      - pentestercrab 5y ago
        The fivefold repetition rule requires no claim by the players.
        ineedasername 5y ago
        Ah, true... Given the double criteria for that (lack of pawn movement) it extends things a bit, but there would still be a finite number of moves. However on an info it's chess board there would always be a unique board state possible. That doesn't by any means refute your point, only add a twist to things.
  - elliekelly 5y ago
    Thanks for explaining this, I learned something, too!
- mrfusion 5y ago
  If the universe is finite, does that mean every problem is a constant time algorithm?
  - deleted 5y ago
    [deleted]
  - emerged 5y ago
    We do seem to spend an awful lot of time worrying about infinities when it appears the cosmological horizon is finite. But I guess if we find some way around that we will be prepared.
    - raattgift 5y ago
      In an accelerating expanding universe like the one we appear to occupy (and the one modelled by our current "concordance" standard model of comology), the comoving horizon is at constant comoving distance. Cast into more Earth-centric coordinates, it is at a finite spatial distance at all finite times. However, there is no reason to expect that a timelike worldline rooted at "here and now" (converting a chosen comoving coordinate into the origin of spherical coordinates for a Eulerian observer) cannot be extended into the infinite future, and at +infinite time the horizon will be at an infinite spatial distance in this system of coordinates. We don't even need to say anything about the matter content of the Hubble volume at any time, anything about -infinite time, or anything about how various measures of entropy fit in; all of these can generate infinities that defy easy (and possibly any) removal in a universe similar to the concordance model. A taste of this can be found at https://en.wikipedia.org/wiki/Cosmological_horizon#Future_horizon https://en.wikipedia.org/wiki/Cosmological_horizon#Future_ho... More deeply and technically, Baez's "Struggles with the Continuum" is great A smooth manifold tends to generate infinities and infinitesimals, and all our fundamental physical descriptions of the universe we inhabit are (at least at present) defined on a Lorentzian spacetime, which is a smooth manifold. He discusses practical reasons to [a] worry about infinities and [b] to work with them anywhere because they might not be removable. https://arxiv.org/abs/1609.01421 https://arxiv.org/abs/1609.01421 (§5 starting on p. 27 is directly relevant, and the concluding §6 is pithy).
  - 5y ago
colejohnson66 5y ago
That’s already a thing with Tic-Tac-Toe.[0] Granted, Tic-Tac-Toe is exponentially less complicated than Chess. [0]: https://xkcd.com/832/ https://xkcd.com/832/

shadowgovt 5y ago

BRB air gapping every single device I own and setting my internet router on fire. ;)

munk-a 5y ago
BRB computing several billion bitcoin hash completions on my Casio.
- anyfoo 5y ago
  Serious question: Is computing cryptographic hashes, by any measure, actually NP-hard? Computing a single hash seems pretty constant to me. Or is there an alternative way to formulate the problem on a higher level, so that cracking cryptographic hashes is NP-hard?
  - deleted 5y ago
    [deleted]
  - staticassertion 5y ago
    Computing any hash isn't, but finding a preimage is NP.
    - anyfoo 5y ago
      Can you elaborate? Is it because a non-deterministic automaton would find the solution immediately (by trying all hashes at once), but a deterministic one of course wouldn't? I think I want to know in more detail why finding a pre-image is non-deterministically polynomial (though I might have answered that to myself with the sentence before), and more importantly why it's deterministically non-polynomial, and on what. Annoying, I took theoretical computer science in university and used to have a better grasp on this, but apparently that part of complexity theory atrophied by now.
      - deleted 5y ago
        [deleted]

meepmorp 5y ago

This is the way.

mikewarot 5y ago

While we're at it... the halting problem CAN be solved, for a computer with N bits of state, in a time proportional to 2^N. It remains unsolvable for Turing machines, however. 8-)