News for hackers. Stuff that matters.
Re:A proof P = NP was accidentally published in TOCT by emerged on Monday July 19, 2021 @05:28PM (#27887457)
Too late, no take backs. P now equals NP and we must live with the consequences!
Re:A proof P = NP was accidentally published in TOCT by mikewarot on Monday July 19, 2021 @08:18PM (#27888798)
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-)

Re:A proof P = NP was accidentally published in TOCT by shadowgovt on Monday July 19, 2021 @05:31PM (#27887484)
BRB air gapping every single device I own and setting my internet router on fire. ;)
Re:A proof P = NP was accidentally published in TOCT by munk-a on Monday July 19, 2021 @05:53PM (#27887673)
BRB computing several billion bitcoin hash completions on my Casio.
Re:A proof P = NP was accidentally published in TOCT by anyfoo on Monday July 19, 2021 @06:03PM (#27887778)
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?
Re:A proof P = NP was accidentally published in TOCT by staticassertion on Monday July 19, 2021 @06:07PM (#27887835)
Computing any hash isn't, but finding a preimage is NP.
Re:A proof P = NP was accidentally published in TOCT by anyfoo on Monday July 19, 2021 @06:17PM (#27887939)
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.

Re:A proof P = NP was accidentally published in TOCT by shadowgovt on Monday July 19, 2021 @06:40PM (#27888111)
You basically have the right idea. The pre-image can be any arbitrary size (in fact, there are an infinite number of pre-images that will hash to the same value).

As useful rule of thumb, the way I learned to think about NP was the mnemonic "nifty proof." Problems in NP are not known to have a polynomial-time solution, and are not known to have no polynomial time solution; that's the million dollar question. What they are known to have is a polynomial time validation.

So it might take some heinous amount of time to find the pre-image of the hash, but determining if a given input string is the pre-image of the hash is polynomial on the number of characters in the pre-image (just run the hash function).

Re:A proof P = NP was accidentally published in TOCT by anyfoo on Monday July 19, 2021 @06:43PM (#27888136)
Correct me if I'm wrong: So n is actually the size of the hash. That's indeed exponential if you try to brute force it, but a non-deterministic automaton would still give the answer immediately.
Re:A proof P = NP was accidentally published in TOCT by freemint on Tuesday July 20, 2021 @06:18AM (#27891931)
A non-deterministic automata can you give an answer after n steps which is polynomial.

NP is the class of problems that can be solved in polynomial time by a non-deterministic automaton.

Re:A proof P = NP was accidentally published in TOCT by anyfoo on Tuesday July 20, 2021 @02:38PM (#27897494)
That much was clear, and I believe also implied in my answers?
Re:A proof P = NP was accidentally published in TOCT by freemint on Tuesday July 20, 2021 @04:59PM (#27899250)
If what I said was your mental state then you are not wrong.
Re:A proof P = NP was accidentally published in TOCT by smnrchrds on Monday July 19, 2021 @05:57PM (#27887723)
How will you be right back after that?
Re:A proof P = NP was accidentally published in TOCT by ineedasername on Monday July 19, 2021 @06:16PM (#27887925)
Assuming supplies on hand?

1)A 5 gallon bucket of gasoline

2) a shop vac w/o a filter & the hose stuck in the bucket to disperse it into the air as a fine mist

3) a bottle rocket sent through the front door (from across the street, preferably)

You know, I've never really though about how to make a homemade fuel air bomb before. It's a bit disturbing that it probably wouldn't be much harder than the above.

Re:A proof P = NP was accidentally published in TOCT by BenjiWiebe on Tuesday July 20, 2021 @01:41PM (#27896751)
The shop vac would probably actually ignite the fumes. And I think the GP was referring to the inability to be right back (here, online) after destroying his internet connection.
Re:A proof P = NP was accidentally published in TOCT by ineedasername on Monday July 19, 2021 @06:11PM (#27887877)
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.
Re:A proof P = NP was accidentally published in TOCT by jcranmer on Monday July 19, 2021 @06:35PM (#27888067)
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.

Re:A proof P = NP was accidentally published in TOCT by ineedasername on Monday July 19, 2021 @07:20PM (#27888390)
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?)

Re:A proof P = NP was accidentally published in TOCT by PeterisP on Monday July 19, 2021 @07:34PM (#27888498)
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.
Re:A proof P = NP was accidentally published in TOCT by agalunar on Monday July 19, 2021 @08:09PM (#27888731)
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.
Re:A proof P = NP was accidentally published in TOCT by ineedasername on Monday July 19, 2021 @08:55PM (#27889015)
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.

Re:A proof P = NP was accidentally published in TOCT by pentestercrab on Monday July 19, 2021 @09:43PM (#27889280)
The fivefold repetition rule requires no claim by the players.
Re:A proof P = NP was accidentally published in TOCT by ineedasername on Tuesday July 20, 2021 @07:06PM (#27900400)
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.

Re:A proof P = NP was accidentally published in TOCT by elliekelly on Tuesday July 20, 2021 @09:57AM (#27893770)
Thanks for explaining this, I learned something, too!
Re:A proof P = NP was accidentally published in TOCT by mrfusion on Monday July 19, 2021 @07:53PM (#27888622)
If the universe is finite, does that mean every problem is a constant time algorithm?
Re:A proof P = NP was accidentally published in TOCT by davrosthedalek on Tuesday July 20, 2021 @08:08AM (#27892755)
I think you also need to assume that spacetime is discretized. Otherwise, two particles have already an infinite phase space (their distance). I don't think the uncertainty principle is enough.
Re:A proof P = NP was accidentally published in TOCT by emerged on Monday July 19, 2021 @09:26PM (#27889200)
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.
Re:A proof P = NP was accidentally published in TOCT by raattgift on Tuesday July 20, 2021 @06:27AM (#27892011)
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_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 (§5 starting on p. 27 is directly relevant, and the concluding §6 is pithy).

Re:A proof P = NP was accidentally published in TOCT by bawolff on Monday July 19, 2021 @11:43PM (#27889838)
No,because you don't have to execute a procedure in order to construct it.

I.e. we can talk about Turing machines with infinite tapes without actually making one with an infinite tape.

Re:A proof P = NP was accidentally published in TOCT by Hercuros on Tuesday July 20, 2021 @02:37AM (#27890711)
It's also important to realize that the standard Turing machine doesn't actually have an infinite tape, but rather it has a tape that can grow to hold an arbitrarily long, but still finite, sequence. At any point during the execution of the Turing machine, only a finite part of the tape will be occupied.

So we can construct approximations of it in the sense that we can create computers with varying, finite amounts of RAM. This might seem like a pedantic/obvious point to make, but it is actually also possible to design abstract computational machines that operate on truly infinite quantities, like a machine that has random access to an infinite, uncomputable sequence.

From a simplicity perspective, it also makes more sense to consider machines with an arbitrarily large amount of RAM (you can always hotplug more RAM), compared to setting some arbitrary limit because that is the most RAM we happen to be able to achieve in this universe.

Re:A proof P = NP was accidentally published in TOCT by hypertele-Xii on Tuesday July 20, 2021 @05:49AM (#27891753)
> random access to an infinite, uncomputable sequence.

I.e. a (cryptographic) random number generator?

Re:A proof P = NP was accidentally published in TOCT by colejohnson66 on Tuesday July 20, 2021 @09:31AM (#27893444)
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/

Re:A proof P = NP was accidentally published in TOCT by meepmorp on Monday July 19, 2021 @05:58PM (#27887739)
This is the way.