Technical Report 2010-003

COMPUTING A PROPERTY ON STRUCTURES

Nikolay Mirenkov
December 15, 2010

Office for Planning and Management
The University of Aizu
Tsuruga, Ikki-machi, Aizu-Wakamatsu City
Fukushima 965-8580, Japan

Technical Report 2010-003
Title:
Computing a property on structures

Author:Nikolay Mirenkov
Key Words and Phrases:
P≠NP, underdetermined problems, graph Hamiltonicity, enhancing the graph definition
Abstract:
The ability to compute a property on structures in polynomial time depends on the structures
and the property we are going to compute. We analyze such dependences and demonstrate abasis for the existence of algorithms of non-polynomial time leading to the separation of P and
NP. This is based on considering NP problems as one type of “boundary value” problems where
specification of “boundary values” is skipped. We present an example of such a problem and its“boundary values” and discuss some issues related to making theoretical models more practical.

Report Date:
12/15/2010

Written Language:
EnglishAny Other Identifying Information of this Report:
To submit to Communication of ACM and/or to some Internet sides
Distribution Statement:
First Issue: 20 copies
Supplementary Notes:

Active Knowledge Engineering Laboratory
The University of Aizu
Aizu-Wakamatsu
Fukushima 965-8580
JapanComputing a property on structures
Nikolay Mirenkov
The University of Aizu, Japannikmir@u-aizu.ac.jp

The ability to compute a property on structures in polynomial time depends on the structures
and the property we are going to compute. We analyze such dependences and demonstrate abasis for the existence of algorithms of non-polynomial time leading to the separation of P and
NP. This is based on considering NP problems as one type of “boundary value” problems where
specification of “boundary values” is skipped. We present an example of such a problem and its“boundary values” and discuss some issues related to making theoretical models more practical.

1. Preliminary consideration
Most computer scientists and mathematicians believe that
paper is to justify this believe.

[1-2]. ThisLet us consider as a structure of our interest the interval of {0,where for any
in this interval the following equation with the unknown (but twice differentiable)
function
is valid:.

(1)

In fact, we can consider N points within this interval (with). The property
to be discovered is behind the question: is there a point where(2)
For simplicity, we can define some level of accuracy to recognize the equality of(2). The general solution to the equation (1) is1

whered are arbitrary constants. The structure definition does not provide
any basis to determine
d . Based on (2), the question related to theproperty can be rewritten in the following form: is there a point where
⁄

.

(3)

To answer this question, we have to perform some search on possible values of
constants and . Though for the one dimensional structure this search can still
be of polynomial complexity, nevertheless, the example considered is a good
illustration of possible necessity- for “additional determining the boundary conditions” which cannot befind in the structure and property definitions, or- for replacing such conditions by some exhausting search.
“Additional boundary conditions” mean not only some possible values on
structure boundary points, but also some externally defined relations andequations.
Now, let us consider another structure which is our interval (one dimensional
structure) that is closured into a cycle. In this case,⁄ , constantand (3) is transformed into⁄that does not

require “additional boundary conditions” or corresponding search to answer thequestion (2).
These simple examples are just to demonstrate that on one dimensional structure,
where local features in points are defined by an ordinary differential equation,
there are two types of algorithms to compute a property on such structure: withor without “additional boundary conditions depending on the involvement ofarbitrary constants.”
However, if we consider two dimensional structures (for example, asquare) and a partial differential equation (for example, Laplace's equation) for
defining local features in points, the algorithms to compute a property candepend on the involvement of arbitrary functions and on a fact that thesuperposition of any two solutions is also a solution. As a result, such algorithms
2

can be of non-polynomial time. It is important to note once more that “boundary
conditions values related to the arbitrary functions” cannot be just extracted fromdefinitions of the structure and the property. To be obtained, they need an
additional search of possible values. This effect is behind.

2. Underdetermined problems
Problems which require “boundary conditions” of the above mentioned type areexamples of underdetermined problems. There are other forms of them. For
example, a system of linear equations is considered underdetermined if there arefewer equations than unknowns. In fact, the number of equations can be equal tonumber of unknowns, but the maximum number of independent rows (or, themaximum number of independent columns) can be fewer.
The existence of determined and underdetermined problems is a fundamental
basis of the existence of P and NP algorithms. For the P algorithms, which are
related to determined problems, there is no necessity to obtain “boundary
condition values.” For the NP algorithms, which are related to underdetermined
problems, there is no a basis for solution without such values. These differences
separate P and NP. Within the framework of this view, let us consider one more
example where a graph is used to represent a structure and a system of linear
algebraic equations is used to represent a property which should be discoveredon this structure.
Let we have a simple graph G = G(V,E) where V is a set of vertices and E is a set ofedges. It is assumed that the graph is undirected one with unweighted edges. It isalso assumed that the number of vertices is N and the number of edges is M. To
simplify the explanation of our approach, we will use an example of graph G (with
M=10 and N=6) depicted by Figures 1-3.
To represent the property of goal computing, a system of N equations (oneequation for each vertex) is defined. Each equation is based on the graphdefinition and on a necessary condition for the Hamiltonicity, requiring two
incident edges of a vertex to be involved into a Hamilton cycle.

3

Fig.1. Graph G with M=10, N=6

Fig.2. Adjacency matrix of G

Fig.3. Edge labeling

For graph G specified by Figures 1-3, the system of such equations looks asfollows:
E1 + E2 + E3

– 2H = F

E1– 2H = F+ E4 + E5
E2+ E6 + E7
E3 + E4– 2H = F+ E6+ E8 + E9

E5

+ E8
E7

(4)

– 2H = 3F+ E10 – 2H = F+ E9 + E10 – 2H = F

where EiF} (i=1,…,10) is a variable representing edge i; its value can be only
H or F which are symbolic parameters (Ei is equal to H if it is involved in a Hamilton
cycle and F if not).
Based on system (4), the property to be computed is defined as follows:
Find a solution of (4) such that a sub-graph of G including only H-edges isconnected.
In fact, it is easy to see that the existence of such solution is necessary andsufficient conditions for the graph Hamiltonicity:- Let a solution exist, then N variables are equal to H, M-N variables areequal to F and the set of H-edges represents a Hamilton cycle; this we
can see after summation of all equations of (4): ∑– NH = (M-N)F
4

and after taking into account that a sub-graph of G including only Hedges is connected.
- Let a set of edges representing a Hamilton cycle exist, then the systemof equations (4) has a solution with EiF}; this we can see after
assigning value H to all edges from the set and value F to all otheredges and after checking that all equations are valid with suchassigning. Assuming that some equations are not valid leads tocontradictions with the graph definition (with subsets of edges incident
to each vertex) and/or with the existence of only two H-edges among
each of these subsets.
Of course, the problem is how to find a solution. A standard linear solver (basedon an elimination method of a cubic polynomial complexity) gives us the following
expressions:
E1 = r1,

E2 = -F+ r4+ r3+ r2- r1,

E3 = 2H+2F- r4- r3- r2,

E4 = r4+ r2- r1,

E5 = 2H+F- r4- r2,

E6 = F- r4+ r1,

E7 = 2H+F- r3- r2,

E8 = r4,

E9 = r3 ,(5)

E10 = r2.

These expressions provide a general solution depending on M-N arbitrary
parameters ri (in our example, 4 parameters) representing “boundary condition
values.” The graph and property definitions do not provide a basis fordetermining ri. An additional search has to be done. We are interested inF}values, so the worst case scenario (which does not expect any specific features of
the graph) for the corresponding search requires
operations (of apolynomial type each). However, if we have a solution, it can be easily (inpolynomial time) verified.
Within the framework of defining features of locality, there is an essential analogy
between the (4) type equations and the (1) type equations. The graph as a set ofvertices and a set of edges can be considered as a structure within a limited two
dimensional area (for example, thesquare) where distances (possibly notall) between vertices are decreased while the number of vertices is increased. As
5

a result, local features in vertices defined by sets of incident edges look like local
features in points defined by differential equations. Therefore, computing someproperties of the graph can lead us to the necessity of “boundary conditions.”
Of course, for graphs with specific features, for example, withg(), the search will be ofoperations (of a polynomial type) and thetotal complexity of the problem will also be of a polynomial level.
On the other hand, in spite of the exponential complexity of the worst casescenario, the (5) type expressions are a good basis for efficient heuristic search
schemes where- frequency of each parameter involvement in the expressions can be used asa priority for making decisions on the parameter values and- symbolic analysis of the updated expression consistency after suchdecisions, as well as appearance of one edge vertices and connectedness ofthe graph, where edges equal to F are removed, can be applied as a special
pruning technique.
The consistency mentioned requires that for each step of decision making, in all
expressions involved, ∑, where is a coefficient at parameter that canbe. For example, for in (5), ∑. In addition,
the value of any should be H or F. Assume, that at the first step a decision toassign H to and is made. Then all expressions including and are also
updated. Before making decision at a second step, all updated expressions arechecked for the consistency and the graph without edges equal to F is checked forconnectedness and appearance of one edge vertices. In this case, the updating
operations transforms expressions of (5) into a form allowing additional symbolic
analysis:
E1 = r1,

E2 = -F+ 2H+ r3- r1,

E3 = 2F- r3

E4 = 2H- r1,

E5 = F,E6 = F,

E7 = H+F- r3,

E8 = H,

E9 = r3 ,6

E10 = H.

From the expression for E3 we automatically obtain value F for r3 and E3, and fromthe expression for E4 we automatically obtain value H for r1 and E4. After that allother Ei obtain their values, too.
3. Bridging gap between theory and practiceSpecifying “boundary conditions” and, in this way, transforming, at least partially,
underdetermined problems into determined ones are a way to make theoreticalmodels be more practical (calls for such necessity, in spite of success of some
practical approaches, are rather strong; see, for example, [3]). On the other hand,practice can help in discovering forms for such specifying and transforming. For
example, to solve the Hamiltonicity problem on German (or European) networksof roads, which were created for centenaries, some history of the road
construction can be extracted to divide the set of edges into subsets with special
features allowing the introduction of systems of algebraic equations (withreasonable level of the determinant rank). Similar ideas can be used for designingdevices/circuits where sets of connections can be technologically divided into
subsets to help in various optimizations. Finally, the introduction of the edge
hierarchy can also be used as a very practical technique for solving large-scale
problems.
These simple observations provide good hints, for example, for enhancing thegraph definition. This enhancing can be done by considering graph as a set ofvertices and a set of edges that is a union of subsets representing a “history” or“hierarchy” of the edge appearance.
As an example, let us consider an idea of hierarchical edges which on the first level
define connections between non-intersected regions, on the second level between non-intersected sub-regions inside the regions, and so on:
{∪

}

… 𝐼;

… 𝐽

;

whe e 𝐼 is the umbe f the hie chic eve s d 𝐽 is the umbe f egi s
on level . We can also assume that the number of sub-regions in a region islimited by constant (ifwe have 𝐽 ≤ 𝐽
and that there is arule (including a full freedom) of assigning vertices in a sub-region for hostingedges representing connections of this sub-region with other sub-regions of thesame hierarchical level.
7

Within such definition, we implicitly defined some “boundary condition values” tosolve Hamiltonicity problem in polynomial time. Considering regions and subregions as super-vertices, at each step of algorithm we can work with graphs
where a property we need can be easily find. This is because of small size graphs
allowing exhausting search and because of appropriate freedom for assigningedges of inter-regional connections. In fact, to find a Hamilton cycle, we can find it
between regions after that inside each region with necessary adjustments
between hierarchical levels. Within a region we need only a Hamilton pathcovering sub-regions. In a case of applying a system of the (4) type, corresponding
equations can be written not only for vertices, but also for regions and subregions. As a result, the number of arbitrary parameters to be considered isdrastically decreased or disappeared at all.
4. Conclusion
NP problems are underdetermined problems where some arbitrary constants/functions or relations are implicitly involved. In general cases such constants/functions or relations cannot be extracted in a complete form from definitions of
the structure and the computing property. And thus, they have to be exhaustively
searched. In other words, external “boundary condition values” cannot be easily
reconstructed through the definition of the structure and internal properties. NP
problems can be considered as “ill-posed problems” requiring some“regularization” in a form of “boundary conditions.” That is why the NP classcannot be equal to the P class. Redefining models by introduction of “boundary
conditions” is a way to solve serious practical problems.
References
1. Lance Fortnow, The Status of the P versus NP Problem, Communication of
ACM, Vol.52, No.9, 2009, 78-86.
2. Richard J. Lipton, The P=NP Question and Gödels Lost Letter, Springer, 2010.
3. Moshe Y. Vardi, On P, NP, and Computational Complexity, Communication of
ACM, Vol.53, No.11, 2010, p.5.

8