Authors: A. A. Frempong
Comments: 11 Pages. Copyright © by A. A. Frempong
By applying differential and integral calculus, this paper covers the principles and procedures for producing the solution of a problem, given the procedure for checking the correctness of the solution of a problem, and vice versa. If one is able to check quickly and completely, the correctness of the solution of a problem, one should also be able to produce the solution of the problem by reversing the order of the steps of the checking process, while using opposite operations in each step. The above principles were applied to four examples from calculus as well as to an example from geometry. Even though in calculus, one normally uses differentiation to check the correctness of an integration result, one will differentiate a function first, and then integrate the derivative to obtain the original function. One will differentiate the trigonometric functions, tan x, cot x, sec x and csc x; followed by integrating each derivative to obtain each original function. The results show that the solution process and the checking process are inverses of each other. In checking the correctness of the solution of a problem, one should produce the complete checking procedure which includes the beginning, the middle, and the end of the problem. Checking only the correctness of the final answer or statement is incomplete checking. To facilitate complete checking, the question should always be posed such that one is compelled to show a complete checking procedure from which the solution procedure can be produced. A general application of P = NP is that, if the correctness of the solution of a problem can be checked quickly and it is difficult to write a solution procedure, then first, one can write a complete checking procedure and reverse the order of the steps of the checking procedure while using opposite operations in each step, to obtain the solution procedure for the problem. Therefore, P is equal to NP. Furthermore, every problem with a complete procedure for checking the correctness of the solution of the problem can be solved in polynomial time.
Category: Combinatorics and Graph Theory
Authors: Anna Knezevic, Greg Cohen, Marina Domanskaya
Comments: 85 pages; this research was partly supported by the School of Electrical Engineering, Computing and Mathematical Sciences of the Curtin University (Australia) whose member is one of the authors (Anna Knezevic)
The permanent’s polynomial-time computability over fields of characteristic 3 for k-semiunitary matrices (i.e. n×n-matrices A such that ��������(����^�� − ��_��) = ��) in the case k ≤ 1 and its #3P-completeness for any k > 1 (Ref. 9) is a result that essentially widens our understanding of the computational complexity boundaries for the permanent modulo 3. Now we extend this result to study more closely the case k > 1 regarding the (n-k)×(n-k)sub-permanents (or permanent-minors) of a unitary n×n-matrix and their possible relations, because an (n-k)×(n-k)-submatrix of a unitary n×n-matrix is generically a ksemi-unitary (n-k)×(n-k)-matrix. The following paper offers a way to receive a variety of such equations of different sorts, in the meantime extending (in its second chapter divided into subchapters) this direction of research to reviewing all the set of polynomial-time permanent-preserving reductions and equations for a generic matrix’s sub-permanents they might yield, including a number of generalizations and formulae (valid in an arbitrary prime characteristic) analogical to the classical identities relating the minors of a matrix and its inverse. Moreover, the second chapter also deals with the Hamiltonian cycle polynomial in characteristic 2 that surprisingly demonstrates quite a number of properties very similar to the corresponding ones of the permanent in characteristic 3. Besides, the paper’s third chapter is devoted to the computational complexity issues of the permanent and some related functions on a variety of Cauchy matrices and their certain generalizations, including constructing a polynomial-time algorithm (based on them) for the permanent of an arbitrary square matrix in characteristic 5 and conjecturing the existence of a similar scheme in characteristic 3. Throughout the paper, we investigate various matrix compressions and transformations preserving the permanent and related functions in certain finite characteristics. And, as an auxiliary algebraic tool supposed for an application when needed in all the constructions we’re going to discuss in the present article, we’ll introduce and utilize a special principle involving a field’s extension by a formal infinitesimal and allowing, provided a number of conditions are fulfilled, to reduce the computation of a polynomial over a field to solving a system of algebraic equations in polynomial time
Category: Combinatorics and Graph Theory