News for hackers. Stuff that matters.
Re:A very old gcc "bug" by ars on Sunday October 25, 2009 @06:37PM (#902271)
You are not the only one who does not understand the halting problem.

The halting problem only says you can not prove every program will (or won't) halt - the general case.

It says nothing at all about any specific case, and there are plenty of programs where you can prove they halt.

And NP just means the solution does not scale well, not that it can't be done.

And NP-complete is something else entirely. It has to do with being able to interconvert all NP-complete problems (i.e. if you solve one you solve all).

There are many NP problems that are not NP-complete. Proving any particular problem is NP-complete, and not just NP is usually a big deal, so don't just throw that term around.

Re:A very old gcc "bug" by jacquesm on Sunday October 25, 2009 @06:48PM (#902279)
It was a quote from the original thread.

As for your explanation, yes, that's correct. The thing that I didn't get about the way they were sparring on the list was that if there is a solution the problem might not be solved in an elegant way, but with the number of variations involved you could simply brute force it.

Then if a solution exists you'll find it, if it doesn't exist then you can report that. After all, if you say you want to put 12 variables in to 7 registers and there is no possible way then there is no possible way. If there is such a possibility the number of permutations is small enough that it could be found anyway.

GCC contributes to the problem by having some overhead that reserves registers that could be saved on the stack for the duration of this part of the computation.