Any demoscener from Mensa?
category: residue [glöplog]
meht: So it took you five minutes to get that far?
adok: Minesweep is a NP problem. In our AI-course we made minesweep solvers using Hidden Markov Models and such name dropping crap. In the end we always had to give in for the random numbers. If your set of Minesweep has a really low density, meaning that there isn't that many bombs available it's quite easy to solve it but when every four square is a bomb things starts to get nasty. Remember that no set of minesweep can be solved without guessing since the first pick always is a guess.
With other words.. Minesweep is impossble to solve with a simple algorithm, and if you do you just got first in line for the Fielding medal since you proved that NP = P..
With other words.. Minesweep is impossble to solve with a simple algorithm, and if you do you just got first in line for the Fielding medal since you proved that NP = P..
sasq: 50 years old.
ekoli:
"Minesweep is impossble to solve with a simple algorithm, and if you do you just got first in line for the Fielding medal since you proved that NP = P.. "
Maybe you need to study again what P and NP are to refresh your memory. A big part of what you said is senseless...
"Minesweep is impossble to solve with a simple algorithm, and if you do you just got first in line for the Fielding medal since you proved that NP = P.. "
Maybe you need to study again what P and NP are to refresh your memory. A big part of what you said is senseless...
Texel: Well, I know that solving Minesweep is considered a NP problem. For large sets of Minesweep with a high density no 100% working solver has been presented. All known solvers must after a set of time use probability which might lead to a wrong decision.
What I meant with that last line was that no known NP problem can be solved in polynomial time, atleast not when it gets to complex, such in this case when density goes up. Ok, you can come up with a quite good heuristic but not a 100% accurate solution. All known NP problems is said to be able to be turn into a CNF-SAT problem. If someone will be able to solve an NP problem in polynomial time with any presented data it will lead to a solution for all NP problems.. perhaps not a trivial one but still.
Well, perhaps I shall just keep my hole shut so you guys can continue measuring your brains instead..
What I meant with that last line was that no known NP problem can be solved in polynomial time, atleast not when it gets to complex, such in this case when density goes up. Ok, you can come up with a quite good heuristic but not a 100% accurate solution. All known NP problems is said to be able to be turn into a CNF-SAT problem. If someone will be able to solve an NP problem in polynomial time with any presented data it will lead to a solution for all NP problems.. perhaps not a trivial one but still.
Well, perhaps I shall just keep my hole shut so you guys can continue measuring your brains instead..
ekoli: if a machine finds out that it can't solve the minefield without random guessing, than it *has* actually solved the problem.
Isn't that just solving a simple second degree equation?
anes: Well... no. Atleast not if you play Minesweep. The rules of the game is that you shall flag all the mines and open all the other squares. If you leave unopen squares you haven't solved the set. :)
NP has the same complexity has P... right? It's just a N or P is just a constant!
ekoli: the rules of the game doesn't make it a problem but a game. in terms of ai, isn't it just the ye olde entscheidungsproblem?
xernobyl: but P is pi, 3.14159..
xernobyl: but P is pi, 3.14159..
what i mean is, guessing if a head or tail will come after a coin toss is not even a problem, yet being an np problem :)
anes: Yes.. I know that Minesweep is a really crappy example of this kind of problems because of the little probability based guessing issue. Going without it would only give even worse results. :)
A quick search on the internet found this one which seamed quite interesting. :)
http://www.claymath.org/Popular_Lectures/Minesweeper/
A quick search on the internet found this one which seamed quite interesting. :)
http://www.claymath.org/Popular_Lectures/Minesweeper/
ekoli, by one hand we have a problem that for all possible cases has no algorithmical solution without guessing; the minesweeper.
By other hand we have P and NP problems.
These things have no relation at all.
There are (at least):
- P problems that have always algorithmical solutions without guessing.
- P problems that have only some algorithmical solutions without guessing.
- NP problems that have always algorithmical solutions wihout guessing.
- NP problems that have only some algorithmical solutions without guessing.
So, as I already said, having always solutions without guessing has no direct relation of being P/NP and being P/NP also doesn't have direct relation to be always or not solvable without guessing.
By the way I read your post, it looks (for me) that you mixed both concepts as if there were any relation.
And also, there are simple algorithms to solve all the solvable minesweeper cases. In the worst of the cases the time needed to solve any of these solvable minesweeper will be non polynomial (NP) if and only if P!=NP (wich is belived to be true but has not been demostrated yet)
I suppose you already known all these things, but in your post it looks very confusing.
Finaly, I have to add that 54 is my favourite number.
By other hand we have P and NP problems.
These things have no relation at all.
There are (at least):
- P problems that have always algorithmical solutions without guessing.
- P problems that have only some algorithmical solutions without guessing.
- NP problems that have always algorithmical solutions wihout guessing.
- NP problems that have only some algorithmical solutions without guessing.
So, as I already said, having always solutions without guessing has no direct relation of being P/NP and being P/NP also doesn't have direct relation to be always or not solvable without guessing.
By the way I read your post, it looks (for me) that you mixed both concepts as if there were any relation.
And also, there are simple algorithms to solve all the solvable minesweeper cases. In the worst of the cases the time needed to solve any of these solvable minesweeper will be non polynomial (NP) if and only if P!=NP (wich is belived to be true but has not been demostrated yet)
I suppose you already known all these things, but in your post it looks very confusing.
Finaly, I have to add that 54 is my favourite number.
Texel: yeah, sorry Texel. I'm not famous for being able to describe with I mean in an understandable way.. ;-)
Bump 2!
Browsing the members list of the HELLIQ high IQ society I discovered a demoscener who is a member of Mensa.
that's interesting. go write a demo about it!
Wow, necromancer!
The have the sign of ancient greek Macedonia.
The subtle art of self promotion that is almost unnoticeable as such.
But oh wait, you're not a demoscener Adok, are you?
But oh wait, you're not a demoscener Adok, are you?
And you are not a member of Mensa, right? :)
win-win
demensa-scener?
Quote:
Browsing the members list of the HELLIQ high IQ society I discovered a demoscener who is a member of Mensa.
hm... claiming high IQ AND payin' 50 bucks to get listed... Judge yourself...
Quote:
hm... claiming high IQ AND payin' 50 bucks to get listed... Judge yourself...
Damn. Wish I'd thought of that website. Nothing like making easy money by simply stroking a random assortment of fragile egos.
