The Execution Time of N Figures Problem Cannot Be Polynomial Written by Jozsef Kiss ( KissCode Systems Kft, Hungary ) Site: http://kcsopensource.com/ Date: 01.01.2018. 0. ABSTRACT There is an existing and non-empty subset of algorithms in which the elements can resolve the N figures ( N queens and its extensions ) problem. These implementations have the property that the Running time of them will be increased dramatically as the size of the chessboard ( and the number of the put figures ) increases. The current world record is known as 27 using queens so the possible valid positions ( no queens attack each others in these every placings ) are known and counted in this size of the chessboard. There are many attempts to reduce the Running time of that implementations ( using bitwise operations, using symmetry, using precalculated attacking map and only valid positions, etc. ) but the tendency cannot be changed considerably. If this could be possible then all of the possible solutions could be known on the chessboard for example in size 100, but we cannot know this information. We would like to show that it is not possible to calculate the valid positions of the N chess figures and to count them quickly or in Polynomial running time. The P!=NP suspicion can be confuted by solving the N queens problem quickly, anyway, which is one of the millennium problems. 1. DEFINITIONS 1.1 Dimension ( D ) the count of all of the used figures to use 1.2 Chess board ( C ) 0 .. ( D ^ 2 - 1 ) ordered sequence for example: the representation of the C4x4: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1.3 Good position this property is declared between any 2 elements of C: Ci and Cj ( i,j contained by N and i,j <= D ^ 2 - 1 ) and means that that 2 elements are not under attack by each other 1.4 Good placing elements in count D of C Chess board in which every 2 elements are Good position 1.5 N chess figures problem to create every Good placings of chess figures in count D on the C chess board in size D and count them 1.6 N chess figures algorithm ( A ) algorithm that can place the chess figures in all of Good placings in an optimized way so there is no part of this algorithm that doesn't work on the N chess figures problem 1.7 Verifying time ( T0 ) the time while the computer can verify any 2 elements of C: they are in Good position it doesn't depend on the current time and nor to the 2 elements of C considered as tiny constant 1.8 Counting time ( T1 ) the time while the computer can count a Good placing also considered as tiny constant as T0 1.9 Running time ( TR ) the full time duration while the implementation of A can start and can end its running so the difference between the end and start times TR only depends on the number of the CPU commands to execute it depends on the value of D indirectly 1.10 Polynomial running time there is a k positive integer as the Running time of implementation of A is O ( D ^ k ) to any value of D 2. ANALYSIS 2.1 Assumption: it is possible to to solve the N chess figures problem by running the implementation of A in Polynomial running time. 2.2 The basic expectations of the N figure problem to the A are: - be able to determine the property of Good position from all elements of any subsequence of C - be able to count the Good placings 2.3 Let the A algorithm to do exactly the aboves and no more. Thus, A is an algorithm that can create all of the subsequences of the Good placings within exactly 0 time and gives only Good placings. Furthermore, A will be able to decide that the subsequences are really Good placings and will be able to count the Good placings. 2.4 The algorithm will do the following jobs: A can decide the Good placing condition of elements counted as D under ( 1 ) 0 + 1 + 2 + .. + ( D - 1 ) = 1/2 * D * ( D - 1 ) calculations. This can happen within ( 2 ) T0 * 1/2 * D * ( D - 1 ) time according to ( 1 ). This new Good position has to be added ( found ++ ) to the count of already found solutions which happens within T1. Let it be ( 3.a ) G = G ( D ) the count of the Good solutions belonging to D Dimension. We cannot know anything about this but on large D values ( 3.b ) G ( D ) < G ( D + 1 ) Then all of the time needed by the calculation of all of the aboves according to ( 1 ), ( 2 ) and ( 3.a ): ( 4 ) TR ( D ) = T0 * 1/2 * D * ( D - 1 ) * G + T1 * G We will use large D values so ( 5 ) D * ( D - 1 ) ~ D ^ 2 Thus, the ( 4 ) expression will be the following using large D values: ( 6 ) TR ( D ) = T0 * 1/2 * D ^ 2 * G + T1 * G Let it be according to 1.10 and ( 6 ): ( 7 ) TR ( D ) = D ^ k T0 * 1/2 * D ^ 2 * G + T1 * G = D ^ k so we will search for the constant k value to this Running time located on left side. 2.5 Let's see the values of k to the ( 7 ) of 2.4. 2.5.1 Let k = 1, then ( 7 ): ( 8 ) T0 * 1/2 * D ^ 2 * G + T1 * G = D 1/2 * T0 * G * D ^ 2 - D + T1 * G = 0 This is a 2nd equitation to D which has at least 1 solution when ( 9 ) ( - 1 ) ^ 2 - 4 * 1/2 * T0 * G * T1 * G >= 0 1 - 2 * T0 * T1 * G ^ 2 >= 0 T0 and T1 are tiny constants but after ( 3.a ), G depends on the size D of the Chess board. Then ( 9 ) cannot be true above a specific value of D according to ( 3.b ). This is the reason of why the ( 7 ) cannot be true to any D when k = 1. 2.5.2 Let k = 2, then ( 7 ): ( 10 ) T0 * 1/2 * D ^ 2 * G + T1 * G = D ^ 2 ( 1/2 * T0 * G - 1 ) * D ^ 2 + T1 * G = 0 ( 1 - 1/2 * T0 * G ) * D ^ 2 = T1 * G D = sqrt ( T1 * G / ( 1 - 1/2 * T0 * G ) ) This can be interpreted if ( 11 ) 1 - 1/2 * T0 * G > 0 Similar to ( 9 ), it can be seen in ( 11 ) that it cannot always be true according to ( 3.b ), so ( 7 ) cannot always be true to any D when k = 2. 2.5.3 Let's see ( 7 ) in general or unmodified case. ( 12 ) T0 * 1/2 * D ^ 2 * G + T1 * G = D ^ k , k > 2 D ^ k - 1/2 * T0 * G * D ^ 2 - T1 * G = 0 D ^ 2 * ( D ^ ( k - 2 ) - 1/2 * T0 * G ) - T1 * G = 0 T1 * G > 0 and D ^ 2 > 0 so the above can be true only if ( 13 ) D ^ ( k - 2 ) - 1/2 * T0 * G > 0 This means that a smallest k value can always be found to a specific D but k cannot be constant: if D increases then k also has to be increased. The reason of that is G ( D ) increases faster than D ^ ( k - 2 ): - in case of queen: G ( D ) can be overestimated as D! / ( 2 ^ D ) - in case of rook: G ( D ) is exactly D! - in case of bishop: G ( D ) is even steeper than D! 2.5.4 So, in cases of k = 1, k = 2 and of general k cases, it can be seen that ( 7 ) cannot be true to any D. Thus, 2.1 Assumption is not true. 2.6 We haven't used the not 0 time needed by the generation of Good placings and not Good placings. This is one further element into the ( 6 ) expression which depends on the D and let it be ( 14.a ) TS = TS ( D ) != 0 According to ( 3.b ), using large D values ( 14.b ) TS ( D ) < TS ( D + 1 ) and, we can see from 2.5.3 the tendency of TS ( D ) ( which is at least the tendency of the G ( D ) because Good and not Good placings are always possible and there will be more and more ) So, this further element cannot decrease the tendency of ( 6 ), it can increase instead. In this way, the 2.5.4 remains true if TS ( D ) != 0. 3. CONCLUSIONS 3.1 The above logic tells us that quick and Running time accordingly to 1.10 is not possible while running the N figure problem solver implementation of A algorithm. 3.2 It can be seen from ( 13 ) that 2.1 would be true in case of T0 = 0 to any D using a constant k value. But having this, the implementation of A could decide a Good placing within 0 time which supposes infinitely fast computer, but this is impossible to build by our current knowledge. 3.3 We didn't consider the queen kind of pieces to put onto the Chess board so 2.5.4 remains true to use any classical kind of chess figure.