back to article That virtually impossible classic compsci P vs NP problem is virtually impossible, say boffins

A trio of computer scientists from the University of St Andrews in Fife, Scotland, has published results showing that a classic chess puzzle dating back 150 years is so computationally taxing that it could take thousands of years to solve. It’s a crushing blow for those trying to win the $1m prize offered for cracking the …

  1. Phil Endecott

    > .... NP‑complete if the answer is also easy to check.

    Not quite. NP means, yes, it's (relatively) easy to check. But the "complete" part is also important. An NP-Complete problem is one which can be shown to be at least as hard as every other NP problem - so, if one can find a P solution to *any one* NP-complete problem, then there are also P solutions to every NP problem, and hence P = NP. On the other hand there are problems that are NP but not NP-complete, so finding P solutions to those problems doesn't prove as much; finding prime factors is (probably) an example of that.

    1. brotherelf
      Headmaster

      While we're nitpicking, and oh boy, is it needed, because in the past weeks of reporting, I have not come across a single reporter that got P and NP right (at least I've not seen anybody say "non-polynomial"), problems that are in NP but not NP-complete only exist if P!=NP. Actually, hang on, the full and empty languages are trivially in P but you don't really have morphisms into them from proper problems, deterministic polytime or otherwise, so yeah, non-NPC problems do exist, even if P=NP, but not in the way I assume you intended.

      (And certainly, somebody will now point out that I've got the direction of the morphism wrong.)

    2. TheVogon

      "is virtually impossible, say boffins"

      So possible then.

  2. Shadow Systems

    So it's a virtual improbability?

    Then it's a finite probability. Plug that number into a... (insert rest of HHG skit here).

    When do I get my money?

    =-D

    1. Citizen99

      Re: So it's a virtual improbability?

      "Then it's a finite probability. Plug that number into a... (insert rest of HHG skit here).

      When do I get my money?"

      You get a bowl of petunias.

      1. Shadow Systems

        Re: So it's a virtual improbability?

        A bowl of petunias? ... Not again! =-)p

  3. Anonymous Coward
    Paris Hilton

    What the hell is #P-Complete?

    "which shows the problem is both “NP‑Complete” and “#P‑Complete”"

    A problem can't be both a bit tricky and proper fucking nutter bastard impossible. If you find yourself in that position then perhaps you have *two* problems. They may look related ...

    Don't confuse "concisely defined" with "rigorously defined" - that way lies madness.

    1. Dan 55 Silver badge

      Re: What the hell is #P-Complete?

      I know what NP complete means because I just Googled an explanation for thickies. It didn't mention #P complete anywhere.

      1. Destroy All Monsters Silver badge

        Re: What the hell is #P-Complete?

        #P definition

        A problem is P‑complete if the solution is easy to find, and NP‑complete if the answer is also easy to check. The paper shows that the n‑Queens problem can be cracked, but not a second time quickly.

        This needs to be reformulated.

        Please El Reg, can we have a diagramming tool to quickly upload a simple back-on-the envelope diagram to explain things?

        1. Naselus

          Re: What the hell is #P-Complete?

          The 'Not a Second Time Quickly' would be a decent title for a Philip K Dick book.

    2. DavCrav

      Re: What the hell is #P-Complete?

      NP-complete talks about testing whether something is true or false, or in other words is or is not a solution to a problem.

      #P-complete talks about how to compute a function, for example computing the number of solutions to a problem, rather than just finding one. Often NP-complete problems have corresponding #P-complete functions, simply by asking to find how many different solutions there are to the NP-complete problem.

  4. John Smith 19 Gold badge
    Coat

    "Ian Gent... from the University of St Andrews in Fife"

    So he's both a gent, and a scholar.

    But bad plays on words aside, again this tells people who are really interested in such stuff more about the solution space and the "shape" that any possible solution must have to work. Which is excellent work.

  5. Mark 85

    Simples

    According to the esteemed Douglas Adams, the answer to this is 42.

    1. Anonymous Coward
      Anonymous Coward

      Re: Simples

      Sorry, must be a Boolean.

      What does 42 coerce to?

      Hrmm, 42 converts to a binary 101010. Is that truthy or falsy...?

  6. Anonymous Coward
    Anonymous Coward

    So what you are saying in the example is that once the 8 queens are placed it's simple to ascertain if they are correctly placed but to place them one by the one the calculation becomes too much because you can only calculate your hypothetical placings of all 8 one at a time.

    Tough one that. The only idea I can think of would involve ruling out combinations that won't work before you start trying to place the queens but then that defeats the purpose of the exercise.

    I've probably understood this wrong so if someone wants to correct me it would be appreciated.

    1. Anonymous Coward
      Anonymous Coward

      > The only idea I can think of would involve ruling out combinations that won't work before you start trying to place the queens but then that defeats the purpose of the exercise.

      Any algorithm is acceptable. But note that there is a trivial solution for all N >= 4:

      https://en.wikipedia.org/wiki/Eight_queens_puzzle#Explicit_solutions

      Therefore I'm not sure what the actual problem under discussion is here - I wish El Reg would write clearly. Or indeed which prize they are talking about. If it's the Clay Mathematics Institute "Millenium Prizes", then N-queens is not one of them:

      http://www.claymath.org/millennium-problems

      Maybe what El Reg is saying (in a roundabout way) is: some [unspecified] problem relating to N-queens is known to be NP-complete; and if you can solve that problem in polynomial time then you will have proved NP=P, and you win the prize (*)

      The prize is also available to someone who can prove NP!=P, i.e. that it's impossible to find such a solution.

      (*) And incidentally you will be a hero for making efficient solutions to many hard computational problems, but will have destroyed most current encryption sytems.

      1. This post has been deleted by its author

      2. Anonymous Coward
        Holmes

        Re. That virtually impossible classic compsci P vs NP problem is virtually impossible, say boffins

        >Therefore I'm not sure what the actual problem under discussion is here - I wish El Reg would write clearly.

        The very first sentence of your link states the problem that the article also refers to: "These brute-force algorithms to count the number of solutions are computationally manageable for n = 8, but would be intractable for problems of n ≥ 20,"

        In the words of the article: "The researchers found that once the chessboard is larger than 1,000 by 1,000, computers can no longer cope with the monumental number of possible squares in which to place a queen."

        1. Anonymous Coward
          Anonymous Coward

          To P, or N to P

          > "The researchers found that once the chessboard is larger than 1,000 by 1,000, computers can no longer cope with the monumental number of possible squares in which to place a queen."

          I think that's just the article author talking. The Wiki suggests that above 20n or so, the current algorithms start to bog down quickly trying to compute all possible solutions. They state that 27n is the highest level of the queen's puzzle fully solved with proofs. I'd suppose someone devoted serious number crunching time to the problem, if 27n is as far as they've managed to get above 20n.

          Consider the race to refine π. That number has been calculated out to many trillions of digits after the decimal point. That's because the pi-calc-problem is not one of those that become rapidly more difficult, like the queen's problem.

          The challenge is to prove that this intractability for certain types of problem is permanent, and we must just live with it. Or conversely, prove that algorithms DO exist that overcome this kind of problem relatively rapidly, no matter how big they get.

          The reason this is important is that many important problems and assumptions hinge on this question, such as the entire public key encryption procedure our banking system depends on. If it does turn out that a really smart person can find a sneaky way to solve the queen's problem for any value of n (and do it before the heat death of the universe), then all heck would break loose. For one thing, the banking system would freak out...

          1. Anonymous Coward
            Anonymous Coward

            Re: To P, or N to P

            > I think that's just the article author talking.

            Quite possible. It's also possible that the algorithms presented in the Wiki article and the one referred to by the article are different - the one referenced in the article may be smarter, but still hits a roadblock at some point.

      3. DavCrav

        "Therefore I'm not sure what the actual problem under discussion is here - I wish El Reg would write clearly. Or indeed which prize they are talking about. If it's the Clay Mathematics Institute "Millenium Prizes", then N-queens is not one of them:"

        This is the NP-complete problem, as it isn't the n-queens problem per se: given an n x n board, with m queens placed on it already, for some 1<m<n, can it be extended to a solution to the n-queens problem? Obviously none of the m queens can be able to take each other, but apart from that trivial restriction, getting good other restrictions is hard.

        1. Charles 9

          I've also heard that any NP-complete problem can be refactored to represent any OTHER NP-complete problem (like, say, Traveling Salesman), which is one reason why you only need to solve ONE to solve ALL.

        2. Anonymous Coward
          Anonymous Coward

          > This is the NP-complete problem, as it isn't the n-queens problem per se: given an n x n board, with m queens placed on it already, for some 1<m<n, can it be extended to a solution to the n-queens problem?

          Thank you, *that* is very clear.

  7. Rol

    I can see a more efficient way of coding the problem and that is by rotating the board by 45 degrees to also generate diagonal co-ordinates.

    Then we would only need four one dimension arrays:- two arrays of length n and two arrays of length 2n-1

    So in an 8x8 board, if we placed a queen at 3,4 we can make x(3)=true y(4)=true and diagx(6)=true diagy(9)=true.

    Subsequent queens need only check one element of each array to confirm a position is valid.

    I had a go at creating the formula to generate diagonal co-ordinates for an n x n board, but I ran out of beer mats and ciggie packets, and whiskey and ciggies, and I'm sure someone did it several centuries ago.

  8. Anonymous Coward
    Anonymous Coward

    Small change

    If I were clever enough to solve P=NP, I could get very rich say mining cryptocurrencies, or I could publish a paper on how I did it and become universally known as the one who broke the modern world for everyone.

    1. Anonymous Coward
      Anonymous Coward

      Re: Small change

      > If I were clever enough to solve P=NP, I could get very rich say mining cryptocurrencies

      I wonder if it is possible to prove P=NP without actually providing a P algorithm for an NP problem.

      It is possible to prove that a number is composite, without learning the factors.

      1. Anonymous Coward
        Anonymous Coward

        Re: Small change

        Quite so, such proofs I think are called non-constructive. So basically you prove that something is possible but without giving a concrete example. Proving that P=NP and creating an algorithm for converting each member of NP into its corresponding member of P may well end up as two different tasks entirely. But at least you'd know it would be P...

  9. x 7

    can someone explain the question?

    1. Anonymous Coward
      Anonymous Coward

      It's the life the universe and everything and the purpose of the paper that covers the McDonald's straws along with with why burger king decided to call their burger a lie (the whopper).

      These mysteries will never be solved unless someone builds a time machine and gets miss Marple and Poirot to have an illegitimate child.

  10. Ian Michael Gumby
    Boffin

    Queens problem is solvable

    If I understand the problem ... you have an N by N matrix where you need to find the set of solutions where you can only have a piece in a square that is neither in the same row or column of an existing piece, nor is on a diagonal to an existing piece.

    I think this is the solution, which I tested on the 4x4 and 5x5 matrices.

    There is a distinct pattern...

    The matrix is numbered 0 thru N-1;

    Lower left is 0,0 while upper right is (N-1, N-1)

    You move from left to right when placing queens.

    Place the first piece in column 0 in any square. (0,k)

    Block out the row;

    Block out the column;

    Block out the diagonal(s) to the right;

    In the next column you place the queen in the square MOD(k+j, N) where j in {2 thru (N-2)}

    If the square is blocked, then the solution attempt fails and you move on to the next possible choice.

    And so on. ...

    This works for N=4 and N=5

    I did it by hand, but will now cobble up a simple program to do it and for larger sets.

    Of course then you have to run thru all of the possibilities to show that this is wrong. But I don't think it is.

    Now where do I submit my solution?

    Note: If the order of queens matters, then its merely an N! for each solution within the set.

    1. Ian Michael Gumby

      Re: Queens problem is solvable part(2)

      Just to expand on it...

      The first part of the problem is to ignore the order of the queens and just find the possible solutions within an N by N matrix.

      The algorithm above works, but its not fully tested. Once you know the possible set of solutions, then its a matter of establishing the order which a simple factorial of N where N is the number of columns.

      5x5 you have 5x4x3x2 which is 120 combinations of queens for each solution set. But that isn't necessary to know the matrix of solutions.

      I guess the issue is that with N = 1000 then if order matters, for each solution set of open cells, I would have to walk thru 1000! permutations and that is what takes time.

      But what am I missing?

      1. DavCrav

        Re: Queens problem is solvable part(2)

        That gives you a solution, which is great, but already known. But the problems are 1) how many different solutions are there? (that's #P-complete) and given some number of queens already placed, can that partial solution be part of a complete solution (that's NP-complete).

        1. Ian Michael Gumby
          Boffin

          Re: Queens problem is solvable part(2)

          The wikipedia answer is a bit more complex than it should be.

          Again I haven't tested my solution and checked it against a brute force method.

          Keep in mind, this is only a part of the solution.

          Assuming I'm correct, its only a part of the solution. It finds the number of cells where you can place a queen, because the order is important.

          Now if I can use this solution, I can easily walk thru an NxN solution where N can be > 1000.

          Then take the count of solutions per NxN matrix. (There should be a pattern to the growth.)

          If true, then you can predict the level of effort to find the solution. For each solution in the set of solutions, for an N by N matrix you would have N! solutions. So you can predict it.

          That is of course assuming I'm correct in my observation that it holds true and it captures all possible solutions. (And that's the big stretch.)

          1. Anonymous Coward
            Anonymous Coward

            Re: Queens problem is solvable part(2)

            As long as there's an N! in your runtime you haven't even started what's being asked. Runtime increases BECAUSE there's of N!m your mission is to remove that.

      2. Anonymous Coward
        Anonymous Coward

        Re: But what am I missing?

        You're looking for an algorithm that avoids enumerating all possibilities and testing them.

        Testing them faster doesn't count.

        Enumerating them faster doesn't count.

        Enumerating less trials and still getting a complete result is what you're aiming for, for certain definitions of 'less' - essentially removing the factorial. Ideally directly enumerating only correct solutions, at which point you won't need to test them.

        Hopefully that should hint at why it's a 'hard' problem.

  11. Anonymous Coward
    Anonymous Coward

    It can't be solved with an algorithm unless you create infinite threads.

    1. Charles 9

      IOW, it can't be solved deterministically, which is one way to class an NP problem (NP stands for Nondeterministic Polynomial).

  12. msknight

    They have failed...

    ...to define, "quickly."

    I do have a method in my head, which may be more efficient than placing queens and checking. However, exactly how fast it needs to be in order to win the prize, is another matter.

    1. Prst. V.Jeltz Silver badge

      Re: They have failed...

      how about you just flag every square covered as a queen goes down? rather than checking it against all the others before it?

      1. msknight

        Re: They have failed...

        Sounds almost as slow as checking every square as a queen goes down, until hitting an actual queen.

        1. Charles 9

          Re: They have failed...

          The problem isn't starting from scratch, as there are relatively simple ways to do it and ensure you get a result.

          The NP-complete problem is to start with a partial board and determine whether or not it's possible to complete that board. It's the existing pieces that complicate the matter since now you have the possibility of no solution and the problem specifically asks yes/no to that. This makes it impossible to use a programmatic approach since the initial layout is random. This puts it in the realm of Traveling Salesman in that the only solution is brute force, which reaches infeasible levels quickly due to its factorial complexity.

          1. msknight

            Re: They have failed...

            The trick with the prize, as far as I can see, is that they have not defined, "quickly." How quick does something have to be, in order to claim the prize?

            it's possible to tighten up the thing through a series of checks, which can knock out series of possibilities that chop down the effort of the brute force. Like in my mind, I look at 6x6 and rather than solve, 6x6, I instead solve 5x6 (30) and add 6. It's easier mentally. Rather than solve the problem... I change the problem until it's solvable.

            Like the joke about the couple who are lost and ask for directions. "If I was you, I wouldn't be starting from here..."

            1. Charles 9

              Re: They have failed...

              But by knocking down the size of the board, you eliminate possibilities that may be necessary to complete the board. How can you be sure the reductions you make don't eliminate necessary positions? For example, in trying to solve a 5x6, you may lock yourself into a position that makes solving 6x6 impossible. How do you prevent this?

  13. VienNT

    I can resolve n queens problem

    At this time my small application can resolve n queens puzzle quite well.

    With N = 1000, it resolves less than 0.1 second. Almost doesn't matter how many queens you place first.

    With N = 10,000, it resolves within 2 seconds. Almost doesn't matter how many queens you place first.

    ..................

    Is it good enough?

    (above tests were running on my laptop, model 2012 with cpu core i5...)

    1. Charles 9

      Re: I can resolve n queens problem

      How many queens do you start out with? For example, with N = 1000, do you use 10 queens? 100? 500? As you increase the number of preset queens, you raise the possibility of blocking out positions for the remaining queens, resulting in the board being a "no solution". Do you check for this?

  14. sbonayab

    Let there be are problem P expressible with n possible solutions. Let there be a parameter NP that codes within it all the n solutions of P. Let the problem P equal to NP. Let P and PN together form an algebraic structure. Then the general polynomial equation of degree n with a field of characteristic zero qualifies to be such an algebraic structure. By the fundamental theorem of algebra a polynomial of degree n has n roots.

    The P and NP problem can therefore defined in a polynomial equation of degree n. Furthermore the various compatible and incompatible combinations of roots are coded in the elementary symmetric equations that can be derived from the general polynomial equation. Solving the P = NP problem in this case would require that we at least find a radical solution of the general polynomial equation. This would also mean that the absolute value of NP is also equal to the absolute value of the products roots of the P = NP problem. Galois Theory does not permit P to be equal to NP in the case of a general polynomial equation of degree n is greater than four. A solution involving transcendental numbers would create imbalance between P and NP. If the P and NP problem has to be solved then all the n roots of the problem have to be extracted from the NP in radical form. The PN can be visualized as the parameter form the P. The P can again be visualized as the polynomial form of NP. The parameter form of the P verses PN problem equals the polynomial form of the same. The NP contains (n!) permutations of the roots of the P verses NP problem.

    Using this line of thinking it can be shown that the P verses NP problem is both P and NP complete.

    This is because the radical solution of the general degree n polynomial can be easily derived and easily verified.

    If the radical solution of the general polynomial equation has been found, then solution of the same is a closed question.

  15. sbonayab

    Algebraic solution of the P verses NP problem

    Let there be are problem P expressible with n possible solutions. Let there be a parameter NP that codes within it all the n solutions of P. Let the problem P equal to NP. Let P and PN together form an algebraic structure. Then the general polynomial equation of degree n with a field of characteristic zero qualifies to be such an algebraic structure. By the fundamental theorem of algebra a polynomial of degree n has n roots.

    The P and NP problem can therefore defined in a polynomial equation of degree n. Furthermore the various compatible and incompatible combinations of roots are coded in the elementary symmetric equations that can be derived from the general polynomial equation. Solving the P = NP problem in this case would require that we at least find a radical solution of the general polynomial equation. This would also mean that the absolute value of NP is also equal to the absolute value of the products roots of the P = NP problem. Galois Theory does not permit P to be equal to NP in the case of a general polynomial equation of degree n is greater than four. A solution involving transcendental numbers would create imbalance between P and NP. If the P and NP problem has to be solved then all the n roots of the problem have to be extracted from the NP in radical form. The PN can be visualized as the parameter form the P. The P can again be visualized as the polynomial form of NP. The parameter form of the P verses PN problem equals the polynomial form of the same. The NP contains (n!) permutations of the roots of the P verses NP problem.

    By the above argument solving the P and NP problem entails the finding the radical solution of the degree n polynomial 4.

    Since Galois Theory does permit radical solution of equation the need arises to seek another approach that yields radical solution functionally expressed in terms of the coefficients of the polynomial. Galois Theory seeks solution via extension and splitting field. It seeks a radical tower via a series of intermediate fields with the splitting field as a subset of the extension field as a condition for solvability. It seeks a solution via the Galois group which is isomorphic to (sn). In the process the theory is entangle by impossibilities in general polynomial equations of degree five and above. In this research such an approach will be avoided. Instead an approach sought sought by which the (x^) term is converted to quadratic factor form.

    When such an approach is used, the radical solution of a degree n polynomial is easily determined and verified.

    The above approach used shows

    1) Radical solution of degree n polynomial is possible and verifiable

    2) the algorithm used is both P and NP complete.

    3) no matter how large the degree the procedures of solving and verifying the solution are not complicated.

    Therefore P= NP

    1. sbonayab

      Re: Algebraic solution of the P verses NP problem

      For any comments and challenges link to:

      https://www.polarisoffice.com/d/2RQtEZFe

    2. Charles 9

      Re: Algebraic solution of the P verses NP problem

      OK, use your approach to solve Traveling Salesman (a known NP-Complete problem) deterministically in polynomial time (IOW, prove Traveling Salesman is actually in P). Prove that and you can conclusively prove P=NP.

  16. sbonayab

    @ Charles 9

    Indeed the travelling salesman problem can be converted to a polynomial equation of degree n if one so desires. In this case x represents the distance between two points in the circuit, the coefficient an-1 represents circuit length, the coefficient ao represents product of the all distances (roots) between points. The other coefficients represent fields containing distances between points as building blocks. If such polynomial equation representation form it depends on what one wants to achieve.

    1. Charles 9

      Re: @ Charles 9

      Traveling Salesman's problem is stated thus. Given n locations, construct the shortest route such that one starts and ends in the same location and visits every other location exactly once. What's the polynomial solution for Traveling Salesman in the general case?

  17. sbonayab

    @Charles

    Yes charles. In this case the circuit points are the towns. The length of the circuit would represent the distance moved and so on

    1. Charles 9

      Re: @Charles

      So what's the general solution for the shortest complete circuit that hits each town except the start/finish exactly once? You say it can be solved; let's see it.

      1. sbonayab

        Re: @Charles

        In this case it is numerically equal to the magnitude of the x^n-1 coefficient of the degree n coefficients, assuming all the derivative elementary symmetric equations encord within them the distances between the towns. The distance between the towns here also represent the roots of the equation.

POST COMMENT House rules

Not a member of The Register? Create a new account here.

  • Enter your comment

  • Add an icon

Anonymous cowards cannot choose their icon