try my puzzles. it includes many forms of science and logic to solve. i will bump it at some point. it is an updated version of the Guiser Gang Riddle Challenge.
deletedabout 7 years
So you are posed with a challenge from a mathematical institute offering a million dollars to whomever finds a solution, which clearly they think is possible, and instead of spending your effort finding a solution you spend that effort trying to prove that it isn't possible.
Nice, that's how millions are made for sure. You go dude, you're going places.
I don't think you're interpreting the challenge correctly. The Millennium Problem actually refers to proving whether P=NP OR P =/= NP. I'm looking at it right now. https://www.claymath.org/events/news/8-queens-puzzle
So the challenge would be to prove that an algorithm exists which can solve the n-Queens problem in polynomial time, which is what I was discussing before. Polynomial time means that if there are n queens, the algorithm must solve the problem in n or some polynomial made of n (n^2 + 2n, for example) steps.This has not been proven to be possible or impossible yet, one way or the other.
deletedabout 7 years
I guess they don't give you a million dollars for solving an easy puzzle, who wulda thunk it, right tatami?
The N queens problem is a type of problem in computer science and mathematics that is classified as NP, specifically "NP-complete", a certain complexity class with the implication that if you can find an algorithm (in polynomial time, tl;dr efficient time) for a single problem in that set, it means that it is possible to find one for any of them. The short of NP problems is that it is computationally difficult to find a solution but easy to verify them if you have one-ex. if you have a 1000x1000 board with 1000 queens, it's super easy to verify the solution-but how do you find one quickly?
This is in comparison to a complexity class called P which is easily computable and solutions found pretty simply. If there's an efficient algorithm for it, it's in P.
The biggest question in modern computer science is does P=NP or are they two entirely classes?
What you're aiming for in this N queens problem is finding an algorithm for a problem that is certified NP-complete, with the definition of NP-complete again meaning that if you can find an efficient algorithm for a single NP-complete problem, not only is that problem in P, but so are all other NP problems.
The consensus of most computer scientists and mathematicians is that it is very likely that P does not equal NP, making such an efficient algorithm literally impossible.
What are you talking about? Writing an algorithm that solves the puzzle? Easy. Writing an algorithm that solves the puzzle in polynomial time? Well that gets tricky. It exists in the NP subset of problems (a solution can be verified as correct or incorrect in polynomial time), but a recent German thesis proved (though may be disproven) that P (subset of all problems that can be solved in polynomial time) =/= NP, which means that this puzzle may not be solvable in polynomial time at all.
