African Poverty Action Thinking Disasters to Prosperity Action Thinking Restoration

Nationwide Anchoring of Productivity and Emergency-Disaster Engineering Affairs on Advanced Science and Technology Research and Development and Demonstration Lemba D. Nyirenda, Ph.D. (Electrical & Computer Engineering) National Expert: Lifelines Disaster Protection, ICT & Energy Systems Operations Research MIEEE, MZAA, MINFORMS, RENG(Z) Fellow Engineering Institution of Zambia, Fellow Computer Society of Zambia Arbitrator and Mediator High Court of Zambia Chief Technical Advisor UNIDO REPRISE-Zambia Project Email: lemba.nyirenda @ undp.org Global Food and Water and Electricity Shortages In the Southern African Region and the world as a whole: food shortages, electricity power blackouts and metropolitan water shortages are the most trouble some. (Nyirenda, L. D., 2007) Electric Power Blackouts Technological Challenge; IEEE Proceedings of the IEEE, (2005) Special Issue: Power Technology & Policy: Forty Years After the 1965 Blackout; World Health Organization, Africa 2000 Initiative for Water Supply & Sanitation) In the case of Zambia , the major contributory factors to the above blackouts are mainly due to two barriers, namely: (1) “ the weak embrace of science and technology national focus in the high offices” and (2) “Zambia’s Research and Development and Demonstration Poverty of the Mind”. Weak Science and Technology National Focus To demonstrate “ the weak embrace of the national science and technology focus in the high offices”. For example, I tried officially over a period of four months to seek audience by appointment with several officials in the highest offices in the land, but to no avail. The purpose of these High Level Science and Technology Executive Briefs was to: (1) share the applicability of my 20 year research findings to national productivity and lifelines infrastructure disaster protection; and (2) Bring to the fore that Zambia has no Laws and regulations that govern the production and distribution of essential resources, commodities, goods and lifelines services under emergency and disaster operating conditions of the national economy. When there is fuel shortage it is confusion . When there is a shortage of electricity it is random blackouts. When there is a bridge washed away the affected regions are cut off from the rest of the nation. When there is a shortage of piped water it is chaotic random supplies. Zambia’s RDD Poverty of the Mind To demonstrate “Zambia’s Research and Development and Demonstration Poverty of the Mind”. For example, I tried officially over a period of 10 years (1995-2005) to promote the idea of think-tank based “National Programme Against Natural Disasters and Technological Disasters” in concert with: the Old National Security Committee of Parliament; the Old University of Zambia; Old ZESCO (Zambia Electricity Supply Corporation); Old Energy regulation Board, and the Old Disaster Management and Mitigation Unit under the Vice President’s Office but to no avail. The Old Zambia Airforce High Command was the exception. PACRO Science and Technology Research Patents Nevertheless, to jump above barriers, two science and technology research patents have been filed with PACRO-Zambia for future generations in Zambia and open-minded institutions in Southern African. These are: (1) Nyirenda, L. D. , (2008): Patent Lodgement No. 41749:“Printed circuit board computerized hole-drilling robot-travelling-salesman-problem-tour construction methodology as a min nD2+ hyperconjugate D1-path linear-spantree-circle using submodular network algebra in a dedekind-cut distance-metrics-weights-measures periodic table” . PACRO-Zambia, January 2008. Lusaka. (2)Nyirenda, L. D. , (2008):Patent Lodgement No. 41828:Universal Productivity-Emergency-Disaster-Recovery “UPEDR” Meter Cluster Arrays for Terrestrial and Deep-Space Applications. PACRO-Zambia, February 2008. Lusaka, Zambia. USA New Deal Challenges The globally visible food, electricity and water poverty-blackouts and many other invisible ones in the national economy wont just go away by themselves, as was the case for the 1935 Economic Depression in the USA. (Heilbroner et al, 1994). The USA depression would not go away because the country was: (1) a recession country, (2) bankrupt of ideas, (3) bankrupt of money, and (4) bankrupt of sustainable lifelines infrastructure for food, medicine, water and sanitation, transportation, electricity, fuel-energy under economic disaster operating conditions. As a way out, the USA New deal Government under President Roosevelt, decided to revive the national economy by replacing and rebuilding the broken down and aged lifelines systems infrastructure through massive government spending. The USA New Deal Government lifelines resurrection programmes nearly failed because they were not spending enough for the fear of being viewed as Socialists. Zambian New Deal Parallel Challenges The Zambian New Deal Government is in a similar situation as was the USA New Deal Government, in that: (1) Zambia is an “Economic Recession Country” who have successfully reached the HIPC (Highly Indebted Poor Country) completion point set by the World Bank and the International Monetary Fund; (2) Zambia appears to be bankrupt of “think-tanks of productive ideas” that can point to individual or corporate solutions that may cause the numerous lifelines blackouts to go away; (3) Zambia is bankrupt of money for lifelines infrastructure development or government investment guarantees; (4) the country’s lifelines systems infrastructure are old or overloaded or breaking down or non-existent in productive development areas. Annex 1 presents eleven types of factors that perpetuate the poverty of the mind blackouts in lifelines utility systems comprising the Zambian National Economy. In part, these poverty of the mind blackouts can be minimized by incorporating them in the Bill of Rights of the New Zambian Constitution. The author’s submission to the National Constitution Conference (NCC) are summarized in Annex 2. National Constitution Conference Challenge The first challenge is to change the way Zambia governs her self in line with Zambia’s prosperity vision encompassing firm and clear short term, medium term and long term national development planning goals. One sure way is through the creation of the “Permanent Prosperity Governance Advisory Council” (PPGAC) enshrined in the New Zambian Constitution. The unique characteristic of the PPGAC is that the institution will endeavour to embrace in perpetuity the reasoned and planned national development agenda independent of which political party is in power. The proposed PPGAC composition of distinguished professionals of integrity (trustworthy, not-corrupt, not-negligent) holding the following Offices of the Republic: (1) Cabinet (secretary to cabinet), (2)Treasury (secretary to treasury), (3) Justice (solicitor-general), (4) legal (attorney-general), (5) Audit (auditor-general), (6)Land (surveyor-general), (7) food and nutrition (food and nutrition director-general), (8) Productivity (productivity-engineer-general), (9) Emergency-Disaster-Recovery (emergency-disaster-recovery-engineer-general), (10) Science & technology (engineering and technical vocation director-general), (11) peace & national security (secretary to military joint chiefs of staff), (12) Unique and Special (unique and special circumstances director-general), (13) Other (short term guest director-general). The second challenge for the NCC is to transform the embedding of: (1) productivity-Engineering Affairs (currently under the Productivity Department in the Ministry of Labour), and (2) Emergency-Disasters-Engineering Affairs (currently under the Disaster Management and mitigation Unit in the Office of Vice President) into an institutional framework that incorporates productivity and emergency-disasters offices starting from Councils, towns, cities, provinces up to Cabinet. This is analogous to how legal Affairs are embedded starting from Council Town Clerk (Lawyer), Land conveyance lawyers, Clerk of the National Assembly, Solicitor-General to Attorney General at Cabinet level. The third challenge for the NCC is to transform the current first degree science and technology achievement to the advanced degree research, development and demonstration achievement. Zambia is such a lonely and dangerous place for scientific creative thinkers, sadly , even among other university intellectuals who should constantly be in pursuit of ideas at the frontier of knowledge. At present , any new scientific body of knowledge that the official-knowledge-elders don’t understand is wrong, unless renown outside world scholars affirm the truthfulness of the novel scientific idea or discovery at hand. This is the most acute case of the Acquired Poverty and Underdevelopment Syndrome (APUS) of the Mind which the NCC should conquer once and for all. The forth challenge is manage NCC as a project for the next 8 months using the [www.onepageprojectmanager.com] showing: (1) Project Leader in Title block; (2) Overall objective specifying quantitative target measure in Title block; (3) Work Objectives, Start Date and End Date Time line, Project Execution Team leaders sub-title block; (4) Discrete connected major task execution schedule arranged column-wise in monthly activity groups above the Startdate-enddate time line,(5) To the left of the Major Task bar tick the major task subsets associated with each work objective, (6) Columnwise the separate work objectives that would produce the overall objective outcome, (7)To the right of the major tasks Identify the code for the executing officer responsible, (8) Columnwise the Full name of the responsible project executing officer,(9) Below the Start date and End date Time line show the running cumulative costs in incremental monthly activity groups, (10) Commentary on progressive Project monitoring and evaluation performance measures . Using these indicators forecast the likelihood of : timely project completion under budget and all principle constituencies taking ownership of the New Zambian Constitution. Finally, it is my sincere hope and prayer that this paper will provoke fruitful debate in parallel with the closed door deliberations in NCC.

WAMPAC Packaged UPEDR Meter LifeLines Maintenance Regime

Electricity/ Transportation /Telecommunications/ Water Networks Packaged UPEDR Meter Cluster Arrays in WAMPAC Preventive Maintenance Regime Balancing Channel Reliability and Environmental Emergencies Dr. Lemba D. Nyirenda, Ph.D. Electrical & Computer Engineering Chief Technical Advisor UNIDO REPRISE-Zambia Project International Expert: Transportation, Energy & ICT Systems Disaster Protection and Lifelines Systems Operations Research Email: lembanyirenda@gmail.com; Phone: +260 977829662 Abstract: The novel application of the packaged UPEDR (Universal Productivity-Emergency-Disaster-Recovery) meter cluster arrays in WAMPAC (wide area monitoring, protection and control) systems to balance Electricity/ Transportation /Telecommunications/ Water lifelines network reliability and environmental emergencies in a preventive maintenance regime offers a cost-effective solution to integrated system planning, operation and economic sustainability. The potential economic benefits include: very high utility network productivity, high emergency operational efficiency and effectiveness, very high route section reliability and associated plant availability, avoided widespread cascade route blockades, and reduced network congestion costs through the mandatory use of emergency bypass routes based on the max-flow min-cut value theorem. Key words: Productivity, Alert, Emergency, Disaster, Recovery Dynamic States Preventive Maintenance Regime.

Universal Productivity Emergency Disaster Recovery Cluster Arrays

Part 1: Integrated Lifelines Networks National Emergency-Disaster Reduction Programme Part 2 :The Universal Productivity Emergency Disaster Recovery (Upedr) Meter The UPEDR meter presented here, provides a universal framework for identifying the dynamic operating states of a functioning [living] system [part, component, structure, body, enterprise, network] at any point in time of its life. The engineered normal operating state [Green] can be described in the virtual UPEDR meter by the apriori prescribed, reference performance indicators of control-level-bands of: [system] governance-peace, [system] economy,[system] adequacy, [system ] security, [system] safety, [system] reliability, [system] maintainability, [system] sustainability. The other transition operating states correspond to deterministic or stochastic confidence intervals with respect to the normal state control level bands. In general, the production system infrastructure is composed of input channels, output channels, production process and several support lifelines such as qualified personnel, electricity, telecommunications, roads, water, money and medical supplies. We desire all production processes with their support lifelines to be in the normal state most of the time for higher and sustained productivity. System performance can be characterized in terms of adequacy, security and safety indicators of each lifeline and the input / output channels in terms of capacity, connectivity and content of the networked subsystems and critical components or parts. Each of these lifelines can experience the dynamic states described above. Thus , total system collapse can occur if one or more of these lifelines enter the Extremis and/or Disaster State. Hence the need for the UPEDR meter to employed at all levels of company or production system. The meter will have hierarchical display modes of the different system indicators denoting system performance in terms adequacy, security and safety of the support lifelines, input and output channel parameters. In this way the corrective control action can be taken before entering the Emergency State. This would form the basis for a Disaster Reduction Plan in a company or production plant. For example, the impact of HIV/AIDS on system security can be monitored through an appropriate HIV/AIDS prevalence indicators for different categories of qualified manpower in a company or centre. Part 3: The value of the UPEDR meter to the National Economy The Zambian national economy is in collapsed state. This is, in part, due to the production processes and their respective support lifelines operating in the emergency or disaster state with low sustained productivity levels in all major sectors such as: lifelines utility services, agriculture, mining, manufacturing, industry, education and health and government departments. For poverty reduction to be realized, it is important for individuals and different production processes nation-wide be operated in the prescribed Normal State for sustained high productivity through the use of the Universal Emergence Disaster Recovery meter.

P v NP Problem Africa Solution

Dedekind-Cut TSP Intractability Barrier Crossing

Lemba D. Nyirenda, Ph.D.

c/o Department of Electrical & Electronic Engineering

University of Zambia, P O Box 32379, Lusaka , Zambia.

lembanyirenda@gmail.com

Overview

This research paper presents a positive definite settlement of the P versus NP problem using the Dedekind-Cut TSP as the representative candidate of problems in the NP-Class in accordance with Cook’s theorem.

The three dimensions for the TSP solution metric space are N_I ( ordered n-source node index set), N_J (ordered n-terminal node index set ), and N_D (n Dedekind-cut weight well-ordering index set). First, the TSP 2D nodal weight matrix is transformed into the 3D Dedekind-cut-value weight matrix VB[N_I x N_J x N_D (free)] by applying the Dedekind-Cantor real number line axiom to each of the n row-weights functional groups and well-ordering N_I and N_J. The nodal row-weights functional group is analogous to the Alkene carbon-carbon double bond functional group in Organic Chemistry. Second, VB is transformed into VC[N_I x N_J x N_D (free)] metric space by associating the D-cut variable with the source-node to terminal-node ratio. Third, VC is transformed into VD[N_D x N_I x N_J (free)] metric space by well-ordering N_D and N_I.

VD is the left solvable group-theoretic 3D Dedekind-cut-value periodic table. VC is the right intractable graph-theoretic 3D Cantor’s array. The periodic table has n horizontal Dedekind-cut sets covering the n-source node functional groups, and n vertical nodal functional groups covering the n Dedekind-cut sets.

The D1-Cut link set in VD provides PBX_b(nx_b,ny_b) and PBY_b(nx_b,ny_b) as the D1-Path composition factor base sets for the submodular optimal TSP solution. Here nx_b is the number of acyclic-head factors, and ny_b is the number of singleton cyclic-tail factors in the minimal set of D1-Path maximal length chains.

The TSP optimal solution submodular D1-Path-Factors fold into a polarized min nd₂₊ max-overlap linear span-tree circle isomorphic to a linear programme 2D corner point convex polygon. The D1-Path-Factor periodic table sections are crosslinked by horizontal Dedekind-cut terminal-node factor groups having diene-like and allene-like cumulated polarization. This is analogous to the isomer of minimum heat of hydrogenation in alkene chemistry.

The TSP D1-Path-Factor folding is such that: the optimal value is in the proximity of the D2-Cut value; the optimal TSP solution has hyperconjugate D1-Path-Factors ranging from ny_b to nx_b+1; and the optimal TSP link-set composition series cumulatively cluster together across the Dedekind-cut sets from k-1/ k to n/n. Thus 50 to 100 percent of the optimal TSP link-set band together in the D1+D2 cut sets independent of n the network size. These characteristics make the TSP a P-Complete solvable decision problem represented by the Dedekind-Cut TSP mathematical programme in accordance with the composition series solvability theorem and the Jordan-Holder subnormal series theorem in Group Theory.

The TSP mathematical programme is patterned on the protein folding problem and has been developed from a connected body of Cross Field Concepts from ten branches of mathematics, computer science, operations research and management science, organic and alkene chemistry, and molecular biology over a period of 23 years.

Summary of results of ten case studies are presented including two fully solved examples for n=5. Thus for the TSP, P=NP. This is demonstrated by solving the Dedekind-Cut TSP Mathematical Programme decision problem modeled as the ‘forward optimality conditions’: Dedekind-cut TSP analysis problem, and the ‘reverse cumulated-polarization objective function’: Dedekind-cut TSP synthesis problem. Thereby crossing the TSP intractability barrier. Therefore, by Cooks theorem: since the TSP is P=NP, then all NP Class problems are P=NP.

Indexing Terms: P=NP, Dedekind-Cantor real number axiom; D-cut travelling salesman problem, protein folding problem, minimum value spanning tree problem, linear spanning tree-circle, submodular mathematical programme, TSP decision problem, discrete optimization, Dedekind-cut metric space, submodular algebra, combinatorial intractability.

1. Introduction

1.1 P versus NP Problem

The P versus NP Problem is one of the seven millennium prize problems for which the Clay Mathematics Institute announced the US$7 million prize fund in 2000. The seven open problems include: the Birch and Swinnerton-Dyer Conjecture the Hodge Conjecture, the Navier-Stokes Equation, the P versus NP Problem, the Poincare Conjecture, the Riemann Hypothesis, and Quantum Yang-Mills Theory.

In 1970, Stephen Cook, as a graduate student at the University of California at Berkeley, showed that all NP (non-deterministic polynomial) problems are similar to each other in innate difficulty, and are transformable in polynomial time to the satisfiability problem in logic. Problems to which all members of the NP Class polynomially reduce are called NP-Hard. (Parker, et al., 1988; Aho, et al., 1974) At the heart of the NP-Class of decision problems in computer science is the notion of ‘easy to verify’, but ‘not easy to solve’. Hence, the P versus NP problem seeks to show that NP-Hard problems can be solved in polynomial time. Stephen Cook and Leonid Levin formulated the P (i.e., easy to find) versus NP (i.e., easy to check) problem independently in 1971.

Here, P stands for polynomial and NP denotes nondeterministic polynomial. This terminology derives from the fact that problems in the NP Class are non-deterministically polynomial-time solvable. In order to qualify for the Class P, a decision problem must actually be resolvable in polynomially-bounded time by a computer. The Class NP includes the decision problem versions of virtually all the widely studied discrete optimization problems, and its subset Class P contained all those that have been conquered with well-bounded, constructive algorithms. The Class P is the set of all problems admitting algorithms of polynomial time complexity.

The best algorithms for NP-hard problems known, have an exponential worst-case time complexity. However, for many NP-hard optimization problems it can be shown that efficient absolute approximation algorithms exist if and only if P=NP. This would mean that the computational intractability barrier would have been crossed. The intractability problem, began as a failure of the human mind when faced with the possibility that a full understanding of the enumerated solution spaces of complex phenomena in many natural situations will take more time than we spend on their analysis, even if many powerful super computers in a multidimensional cosmic cube configuration (Jenkins, 1986) are networked worldwide through the internet. (Barrow, 1998) Therefore, the computational intractability of combinatorial sequences of large connected networks remains to be one of the most formidable impossibility limits. Thereby making the combinatorial intractability barrier as one of the greatest “computational impossibility limit” in the limits of science and the science of limits (Barrow,1998).

The family of NP-Hard problems includes all the problems that have frustrated discrete optimizers for decades, such as: travelling salesman (directed and undirected Hamiltonian cycle), graph-colouring, precedence constrained scheduling, parallel-processor scheduling, knapsack, set covering/packing/portioning, various fixed charge models, and 0-1 integer/mixed-integer programming, Dial-a-Ride Problem (Cordeau, 2006), and Duchenne et al, 2007). These problems are generally referred to as intractable or NP-Hard even in the special 0-1 integer mathematical programme formulation (Cordeau, 2006; Duchenne et al, 2007) , because it would take a prohibitively long time to solve large problems by the fastest computer program that would be written.

1.2 Clay Maths Challenge

Problems such as the TSP that are both NP-Hard and members of the NP Class are called NP-Complete. Therefore, if the status of any member of the NP-Complete Class is resolved. Then the NP-Complete problem of interest will also be resolved.

So far there is no known polynomial time algorithm for solving any NP problem quickly, including the TSP. This has led to the P¹NP conjecture. Nevertheless, a conjecture, even a widely held one such as the P¹NP conjecture, is not a proof. (Parker, et al., 1988; Sommer, et al., 1988; Balas, et al., 2001)

As a result, the Clay Mathematics Institute of the USA, has posed the following question on the www.bhubdub.com website: “Will there be a solution to the theoretical computer science ‘P versus NP’ problem before 5pm CET, Tuesday, January 1, 2013?” As of 28^th October 2009: 12 percent of the website respondents voted ‘YES’ and 88 percent voted ‘NO’. Nevertheless, here for the first time we present a positive definite solution to the ‘P versus NP’ Problem, by crossing the intractability barrier through the Dedekind-Cut TSP Periodic Table (Nyirenda et al,2009).

1.3 Combinatorial TSP intractability barrier Crossing

Here we see that for the TSP, P=NP. Thereby crossing the combinatorial  TSP intractability barrier as shown in Table 4.4. This is  demonstrated by solving the  TSP decision problem modeled  as  the forward: optimality Dedekind-cut TSP analysis problem, and the  reverse: cumulated polarization Dedekind-cut TSP synthesis problem using the objective function and the three optimality conditions of the Dedekind-Cut TSP Mathematical  Programme. (The ten detailed case study results are available on request upon making US$100 research contribution to lembanyirenda@gmail.com per case in Table 4.4).

The crossing of the combinatorial  TSP intractability barrier is demonstrated  by the results of the ten case studies presented together with the two fully solved examples for n=5 and n=17 from TSPLIB95. The minimum value TSP Solution set is embedded in the ‘D1-Path-Factor Cumulated Polarization Linear Span-tree Envelop’ as shown in Table 5 and 6 of appendix 3 for Case 8-n17 asymmetric TSP example. 

Since for the TSP P=NP, a representative NP Class problem; then by Cooks theorem all decision and optimization problems in the NP Class are P=NP.

2. TSP Analysis Problem

2.1 D-Cut TSP 3D metric spaces

Let: W_IJ(d_k) be the Dedekind-cut weight measure for one directed linear-link connecting nodes (I and J) ; N_I[n] = {I = 1 to n} be the source-node well-ordering index set.; and N_J[n] = {J = 1 to n} be the terminal-node well-ordering index set; and N_D[d_n] = { d₁ to d_n} be the Dedekind-cut nodal-weight well-ordering index set provided by the Dedekind-Cantor real number line axiom (Davis,1982).

Then the 2D network weight matrix VA[N_I[n] x N_J[n]] can be transformed into a 3D Dedekind-cut (D-Cut) fully-ordered periodic table FOPT [DC[n] x FG[n]] = VD[N_D[n] x N_I[n] x N_J[n](free)].

The VD metric space provides: n-horizontal D-Cut groups, namely DC(N_I) = {DC1[nd₁], DC2[nd₂], ··· , DC_K[nd_k] , ··· ,

DC_n-1[nd_n-1] , DC_n[nd_n] }; and n-vertical functional groups: FG(N_D) = { FG₁[n], FG₂[n], ··· , FG_I[n] , ···,

FG_n-1[n], FG_n[n]} as shown in Table 3.4 of Appendix 2.

“A pictorial representation of a Dedekind-cut corresponds to a straight line along which all the positive rational numbers are marked in their natural order. Dividing this line into two parts such that the part containing the smaller rational numbers contains no greatest provides a picture of a cut.” (Körner, et al.,1972)

2.2 TSP Group Theoretic Solvability

The question that arises : Does the VD metric space provide a P-complete choice function for the TSP optimal solution set (H^*[n]) as it does for the Spanning Tree Problem (STP)? The answer is YES. This is because the Dedekind-Cut H^*[n] set in VD[N_D x N_I x N_J(free)] = FOPT [DC[n] x FG[n]] is a solvable group having D-Cut subnetwork composition series satisfying the Group Theory Solvability theorem (Baumslag et al., 1968), such that:

for k=1 to n:

(1) 0/1 < 1/2 < 2/3 < · · · < k-1 /k < · · ·< n-1/n < n/n

(2) G^*_Æ[ng₀^*= 0]ÌG^*₁[ng₁^*] ÍG^*₂[ng₂^*]Í···ÍG^*_k[ng_k^*]Í··· ÍG^*_n-1[ng_n-1^*]Í G^*_n[ng_n^*]

(3) [ng₀^*= 0]/n < [ng₁^*]/n £[ng₂^*]/n £ ··· £ [ng_k^*]/n £··· £ [ng_n-1^*]/n £ [ng_n^*]/n =[n]/n

(4) [VDC₀ = 0] < VDC₁^* <VDC₂^* < VDC₃^* < ··· < VDC_k ^*< ··· < DC_n-1^* < VDC_n^*

(5) [VDC₀ = 0] < VDC₁ <VDC₂ < VDC₃ < ··· < VDC_k < ··· < VDC_n-1 < VDC_n

(6) k^th order D-cut subnetwork factor:

G^*_k[ng_k^*] = G^*_k-1[ng_k-1^*] + D^*_k[nd_k^*]

G^*_n[ng_n^*] = H^*[n] optimal TSP set

[ng_n^*]= [n] , optimal TSP set length

k^th order composition series factor: ng_k^* = ng_k-1^* + nd_k^*

k^th order D-cut set: D^*_k[nd_k^*] Ì D_k[nd_k] Î DC_k(N_I)

optimal TSP set value: VDC_n^*= VH^*[n]

k^th order D-cut set value:VD^*_k[nd_k^*] < VD_k[nd_k] < VDC_k(N_I)

Here, the set S1 = { 0/1, 1/2, 2/3, · · ·,k-1/k , · · ·, n-1/n, n/n} is the element by element lower bound for the set of composition series ratios {ng_k^*/n, for k=1 to n} which are also well ordered by “<”. S1 is well-ordered by “<” relation only . The set S1 corresponds to the set of upper diagonal integer fractions in Cantor’s Array. (Kasner; et al., 1989)

The set S1 is derived from the adjusted factor set of the inverse digamma function additive Series. (Tuma,1989) The combinatorial TSP feasible sets are bounded by the gamma function multiplicative series of the factor set :

S2 = {1, 2, 3, · · ·,k , · · ·, n-1,n}. (Tuma,1989)

2.3 D-Cut TSP mathematical programme

The Dedekind-Cut TSP optimal solution characteristics can be summarized into a Linear Span-Tree Circle Mathematical Programme. The optimal TSP solution satisfies the submodular algebra objective function, subject to the three optimality conditions in the Dedekind-Cut Periodic Table domain. The three optimality conditions are: the Optimal-value D2-cut-value proximity inequality; the max-cumulated boundary D1-Path-Factor hyperconjugation inequality; and the optimal Dedekind-cut composition series clustering inequality.

The TSP optimal solution is constructed as a submodular D1-Path-Factor linear span-tree circle (LSC). The LSC is a crosslinked periodic table folding having cumulated nodal functional group boundary polarization similar to dienes and allenes in alkene chemistry.(Ege, 1984; Morrison, et al.,1973) It is constructed as a sequence of min nd₂₊ max-overlap submodular-divisions of max-cumulated hyperconjugate D1-Path-Factor tableaus. The number of D1-Path-Factors range from ny_b to nx_b+1. The optimal TSP solution satisfies the optimality conditions of the Dedekind-cut TSP mathematical programme as demonstrated in Section 2.3 and Section 4.3.

The TSP mathematical programme has been developed over a period of 23 years (1986-2009) using cross field concepts from mathematical programming (Gass, 1969; Hillier, et al.,1969; Rosen, 1999) , submodular algebra (Parker, et al., 1988; Chen,1990; Nyirenda,(1991) and principles which imply the Axiom of Choice in axiomatic set theory (Suppess, et al.,1972) , real analysis (Royden, et al., 1988; Boyer,1949; Körner, et al.,1972; Grattan-Guinnes, 1980), gamma and digamma functions (Tuma, et al., 1989), combinatorial and discrete mathematics (Cohen,1978; Stout ,1982; Rosen, 1999; Nemhauser, et al., 1988; Parker, et al., 1988), combinatorial geometry (Preparata, et al., 1985),topology (Hocking,et al.,1961; Coxeter, 1973); general topology (Lipschultz,1965) , graph theory (Diestel, 1990; Deo, 1974 ), group theory (Baumslag, et al., 1968), the periodic table and alkene chemistry (Masterton, et al., 1969; Ege, 1984; Morrison , et al.,1973) and molecular biology (Fraenkel, 1993; Freifelder,1985).

2.3.1 Submodular Algebra Formulation

The submodular algebra formulation of the optimal TSP solution is represented as a D1-Path linear span-tree circle (LSC) folding in the D-cut periodic table domain using the augmented FOPT (fully ordered) Tableau or POPT (partially ordered) Tableau D-Cut TSP mathematical programme:

Objective Function:

VH* [n] = min Value { VH^D [n] }

H* [n] = min Value LSC

H^D[n] = min nd₂₊ Cumulated-polarization D1-Path-Factor Submodular Division Linear Span-tree Circle (LSC)

=min nd₂₊ [FOPT or POPT(PBX_b[nx_b,ny_b]={ P_x[nf_x], x=1 to nx_b}),(CumJD-maxoverlap Submodular Division (¸))]

or

= min nd₂₊[FOPT or POPT (PBY_b[nx_b,ny_b]={ P_y[nf_y], y=1 to ny_b}),(CumJD-maxoverlap Submodular Division (¸))]

Subject to:

(1) Optimal-value D2-Cut-Value proximity inequality

(VDC₁[n] ) < (VDC₂[n] = [VH^D[n] ± D₂ ] ) < (VDC₃[n] )

(2) Cumulated Polarization D1-Path factor hyperconjugation inequality

(ny_b ) £ nD1-Path-Factor(+)^D £ (nx_b+ 1 )

nCumJD = Total number of horizontally Cumulated (D,J) factor-groups

= nhJ (diene type) + nhx (Allene type)

(3) Dedekind-Cut Composition Series Clustering Inequality

k= 1 to n

(k-1)/k £ ng_k^D / n = [ (ng_k-1^D/n) + ( nd_k^D/n)] £ n /n

··· ··· ···

ng_n-1^D / n = [(ng_n-2^D/n) + ( nd_n-1^D/n)] = n /n

Here, the base index b=1. PBX_b(nx_b, ny_b) is the minimal D1-Path base set composed of maximal length chain of (I/J d1) factors in the D1-Cut set DC₁(N_I) ={ W_IJ,(I/J d1)} in FOPT (fully ordered) Tableau or POPT (partially ordered) . The maximal length chains are obtained using the submodular addition groupoid of the D1-cut set . PBX_b(nx_b, ny_b) is reducible to PBY_b(nx_b, ny_b) using the submodular division groupoid of subsets of D1-Paths having common singleton cyclic-tail-factors. Their construction is demonstrated in Table 3.5 in Appendix 2 (US$100 research contribution).

Here, nx_b = number of acyclic-head-factors in PBX_b and ny_b= number of singleton cyclic-tail-factors in PBX_b . PBX_b(nx_b, ny_b) is the Acyclic-head-factor D1-Path base set, and PBY_b(nx_b, ny_b) is the Cyclic-tail-factor D1-Path base set. They constitute the composition factor set for the optimal TSP solution.

2.3.2 Optimal value proximity Constraint

The optimal TSP link-set (H* [n]) clusters around the D1+D2 cut set composition series. This is independent of the network node size and irrespective of whether the D-cut sets are fully-ordered or partially-ordered in the VD periodic table. Therefore, the lower bounds and upper bounds on the total weight of the optimal TSP set value VH* [n] is given by the Optimal-value D2-cut-value proximity inequality.

VDC₁ < (VDC₂ = [VH* ± D₂ ] ) < VDC₃

Here the optimal TSP value is in the proximity of the threshold value VDC₂ such that : W_L = VDC₁, the D1-Cut link-set value; W_T = VDC₂, the D2-Cut link-set value; and W_U = VDC3 the D3-Cut link-set value in VD.

2.3.3 Cumulated Polarization Hyperconjugation Constraint

The optimal TSP solution forms a hyperconjugate D1- Path-Factor linear span-tree circle analogous to a linear programming 2D corner point convex polygon. The D1-Path-Factor tableaus are cross-linked through the cumulated polarization of the horizontal D-Cut J elements. Each cross-linked D1-Path-Factor tableau, in the linear span-tree circle, subtends a subset of vertical D-cut nodal functional groups providing horizontal d-cut (I/J d_k) factor sets. The horizontal D-Cut J elements, in the vertical nodal functional groups, have {I1/J1da, ... , I2/J1db, … ,I1/J1dc, …, I2/J1dx : J1/J2d1} diene-like or {I1/J1dx, I2/J1dx, I1/J1dx, …, I2/J1dx: J1/J2d1} allene-like cumulated polalization at the boundary. Diene and allene double bond carbon structures are defined in alkene chemistry. (Masterton, et al., 1969; Ege, 1984; Morrison, et al.,1973)

The H* [n] linear span circle satisfies the cumulated D1-Path factor hyper-conjugation inequality:

ny_b £ nHypD1-PathFactors £ (nx_b + 1 )

Here, b = 1 is the base index; nx_b> 0; and , ny_b > 0 .

2.3.4 TSP Composition Series Clustering Constraint

The optimal TSP composition series cluster together in accordance with the Dedekind-cut choice inequality:

k-1 /k £ (ng_k* = ng_k-1* + nd_k*)/n £ n/n presented in Table 3.4 in Appendix 2 (available on request upon making a US$100 research contribution to lembanyirenda@gmail.com).

The clustering inequality guarantees 50 to 100 percent of the optimal value link set to be included in D1+D2 Dedekind-cut sets in the fully or partially ordered periodic table. This is independent of the network node-set size n.

3. TSP Optimal Solution Linkages

3.1 Alkene Chemistry Linkages

In Alkene Chemistry the functional group is the carbon-carbon double bond. In a monotonically well ordered D-Cut-Value periodic table, each row-simplex in a nodal weight matrix VA[N_IxN_J] becomes a vertical D-Cut-Value functional group in VD[N_DxN_Ix N_J(free)], as demonstrated in Table 3.4 in Appendix 2(available on request upon making a US$100 research contribution to lembanyirenda@gmail.com). . Each row simplex is analogous to a period in Mendeleevs Periodic Table. (Masterton, et al., 1969)

The weight matrix VA[N_I x N_J ] provides two sets of n nodal functional groups (NFG) or n-periods . These are: the row-wise {FG_I[n]} set and the column-wise {FG_J[n]} set as shown in Table 3.1. The role of the row-wise functional group in VA[N_I x N_J] is analogous to the Alkene carbon-carbon double bond functional group in Organic Chemistry. (Ege, 1984; Morrison, et al., 1973)

The D1-Path-Factor hyperconjugated structure of the TSP optimal solution is analogous to the most stable “Max-Overlap hyper-conjugated Alkene isomer” having the minimum heat of hydrogenation in the atomic periodic table. (Masterton, et al., 1969) The minimum energy isomer is made using the “Max-Overlap Principle” and is a hyperconjugated chain consisting of cumulated carbon double bond strings (allenes), conjugated carbon double bond strings (dienes), and single-isolated carbon double bond strings. (Ege, 1984; Masterton, et al., 1969; Morrison , et al.,1973)

Here, the first order Dedekind-cut linear path factors are analogous to the alkyl groups attached to the doubly-bonded carbon atoms. The greater the number of alkyl groups attached to the doubly-bonded carbon atoms the more stable the alkene. (Ege, 1984; Morrison , et al.,1973)

3.2 Linear Programming Linkages

The TSP optimal solution is a convex polygon whose sides consist of factors of D1-Path maximal chains and the corner points provide the intersection of the linear D1-Path boundary extreme points. The extreme points form higher order D1₊ links in the linear spanning tree-circle. The convex polygon formed is similar to a two dimensional convex region of the constraint set of a Linear Programme. (Gass, 1969; Hillier, et al.,1969) The synthesis of the D1-path base set is demonstrated in Table 3.5. Thus the TSP becomes a linear programming problem of folding the maximal chain D1-Path factors into a hyperconjugate extreme point convex polygon or linear spanning cycle of minimum value. This is similar to the protein folding problem. (Fraenkel , 1993; Freifelder,1985)

3.3 LSC Space Construction Procedure

The data sources for the ten case studies presented are in appendix 1. The construction of VD from VA the TSP nodal weight matrix is demonstrated in Tables 3.1 to 3.4 in appendix 2. The fully ordered periodic table VD presents a P-Complete Dedekind-cut TSP solution space requiring: first, the construction of PBY_b(nx_b,ny_b) the minimal D1-Path composition factor base set as shown in Table 3.5 in appendix 2; second, align the nodal functional group tableaus in VD to be in one-to-one correspondence with the linear D1-Path set to provide the max nd₁ LSC as in Table 3.6 in appendix 2; third, arrange the D1-Path nodal functional group tableaus into factorized max-overlap cumulated polarization sequence envelop as in Table 3.7 in appendix 2 ; fourth, construct the cumulated min nd₂₊ Hyperconjugate D1-Path-Factor Linear Spanning-tree Circle TSP solution space satisfying the optimality conditions of the D-Cut TSP mathematical programme as in Table 3.7 in appendix 2(available on request upon making a US$100 research contribution to lembanyirenda@gmail.com); fifth, select the minimum total value LSC set as the optimal TSP solution set as shown in Table 3.7 in appendix 2. The related patented TSP solution methodology is summarized in appendix 3 (available on request upon making a US$100 research contribution to lembanyirenda@gmail.com).

4. Conclusion

4.1 Third missing TSP dimension

The discovery of N_D, the third missing dimension of the TSP solution space, has made it possible to construct the TSP group theoretic periodic table in which 50-100 percent of the optimal TSP set clusters in the D1+D2 cut sets independent of the network node set size (n).

The significance of N_D , the Dedekind-Cantor real number line, is analogous to the fourth dimension of time in the theory of relativity by Albert Einstein.

4.2 TSP Intractability Barrier Crossing

The construction of the TSP submodular algebra mathematical programme, for validating and constructing optimal TSP solutions in polynomial time, has provided for the first time a bridge for crossing the once impossible “Intractability Barrier” for the “enumeration required” Combinatorial TSP . The tractability of the Dedekind-cut TSP is demonstrated in part by the ten case study findings summarized in Tables 4.1 to 4.3 (available on request upon making a US$100 research contribution to lembanyirenda@gmail.com).

4.3 NP Class P Status

Here we see that for the TSP, P=NP. Thereby crossing the combinatorial  TSP intractability barrier as shown in Table 4.4. This is  demonstrated by solving the  TSP decision problem modeled  as  the forward: optimality Dedekind-cut TSP analysis problem, and the  reverse: cumulated polarization Dedekind-cut TSP synthesis problem using the objective function and the three optimality conditions of the Dedekind-Cut TSP Mathematical  Programme. 

The crossing of the combinatorial  TSP intractability barrier is further clarified by the results of the ten case studies (n=4,5,6,6,8,8,16,17,33,67) presented together with the two fully solved examples for n=5 and n=17 from TSPLIB95. The minimum value TSP Solution set is embedded in the ‘D1-Path-Factor Cumulated Polarization Linear Span-tree Envelop’ as shown in Table 5 and 6 of appendix 3 for Case 8-n17 asymmetric TSP example .

Therefore, by Cooks theorem: since for the TSP, the representative NP Class problem, P=NP; then all decision and optimization problems in the NP Class are P=NP.

4.4 P versus NP Millennium Prize Problem

The Clay Mathematics Institute of the USA, who awarded the One Million US$ Millennium Prize for the P versus NP problem , have posed the following question on the www.bhubdub.com website : Will there be a solution to the theoretical computer science P versus NP problem before 5pm CET, Tuesday, January 1, 2013? As of 28^th October 2009: 12 percent of the website respondents voted ‘YES’ and 88 percent voted ‘NO’.

Nevertheless, on 14^th December, 2009 : a positive definite settlement of the P versus NP millennium prize problem is presented using the TSP as the representative candidate of problems in the NP-Class. The universal utility of the finding that P=NP for the TSP is the design and development of the Universal Travel-Connection Productivity Tool.

4.5 Universal Travel-Connection Productivity Tool

If one examines the everyday activities involving people and their vehicles, and all mobile living things . They execute their everyday business traveling round and round in circles touring source nodes and terminal nodes to fit various livelihood purposes at hand. The circular perimeter paths traversed in normal routine, alert route, emergency routine , disaster routine, revival routine, recovery routine and restoration routine may cover very small, small, large and/or very large geographical areas with varying tour cycles. All this cyclic traveling is being undertaken by traveling sales men and women from all walks of life ranging from children walking to school, parents driving their children to school , the traveling business man, the traveling postman, the traveling fireman, the traveling preacher-man, the traveling judge and the traveling tramp ship on high seas and future deep space exploration travel. This constitutes the universal traveling salesman problem (TSP).

All TSP travel is oftentimes done routinely as random walk tours. These walks because of “poverty action thinking” , as opposed to “prosperity action thinking”, are carried out at unmonitored great costs in terms of expended scarce and valuable resources of time, money, strength, talents and relationships every minute throughout the world.

Therefore, if random walks of life were transformed into productive walks that are based on a “Universal Travel Productivity (UTP) tool” which promotes “universal prosperity action thinking” in executing everyday cyclic livelihood business connections and travel. Then, the discovery of such a UTP tool , would transform the random walk madness of the rich and poor peoples of the world into peaceful productive walks. Such productive walks would be engineered to be performed within the budget envelop of the available , scarce and valuable resources of time, money, strength, talents and relationships throughout the world every minute.

The needed Universal Travel-Connection Productivity (UTCP) tool is the “ Network Dedekind-Cut-Value Periodic Table” of quantified weights and measures of time, money, strength, talents and relationships to be expended on inter-nodal paths traversed in normal routine, alert route, emergency routine , disaster routine, revival routine, recovery routine and restoration routine. The “ Network Dedekind-Cut-Value Periodic Table” is analogous to the “ Atomic Weight Periodic Table” created by Mendeleev in 1870. (Masterton, et al., 1969).

The UTP tool would be used very effectively and efficiently in the UPEDR (Universal Productivity Emergency Disaster Recovery) meter cluster arrays lifelines systems disaster protection, emergency disaster preparedness logistics planning, and during search and rescue missions during major catastrophic manmade disasters and/or natural disasters. (Nyirenda, 1999-2008; UN ISDR, 2005; Appendix 3)

Acknowledgement

I am greatly indebted to the late Professor Emeritus Roland Schinzinger, of the University of California at Irvine, for having guided and funded the initial stages of the research work and for the unwavering familial support of Dr Drinah Nyirenda, of the University of Zambia, through the provision of financial resources and encouragement over the 20 years of this research work.

Biography

Lemba D. Nyirenda obtained his: bachelor of engineering degree from the University of Zambia in 1976; masters degree in power engineering and operations research in 1983 and doctorate in computer and electrical engineering in 1991 at the University of California Irvine, respectively. He is the Chief Technical Advisor and Project Coordinator of the GRZ-MCT/UNIDO/GEF Renewable Energy Powered Rural ICT services Project for Zambia. He is a past Chairman and board member of the Engineers' Registration Board of Zambia, as well as the past Vice-Chairman and board member of the National Roads Board for Zambia; Fellow of the Engineering Institution of Zambia; Fellow Computer Society of Zambia; Member of the IEEE (USA) and INFORMS (USA); and High Court of Zambia Arbitrator and Mediator. He is also a lecturer in the Department of Electrical and Electronic Engineering at the University of Zambia. His research interests include Energy and ICT systems disaster protection; and integrated development of electricity, telecommunications, and water lifelines infrastructure; management science and operations research. Dr Lemba D. Nyirenda holds two PACRO-Zambia Patents covering the “Universal Productivity-Emergency-Disaster-Recover Meter” and the “Circuit-Board Computerized Drilling Dedekind-Cut TSP Periodic-Table Composition Series Methodology”.

References

Aho, A.V.,J.E.Hopcroft and J.D.Ullman (1974). The Design and Analysis of Computer Algorithms, page 49-54, 363-400.Addison-Wesley, Reading USA.

Balas, Egon and Neil Simonetti. “Linear Dynamic Programming Algorithms for New Classes of Restricted TSPs: A computational Study”. INFORMS Journal on Computing, Vol 13, No. 1, Winter 2001. page 56-75.

Barrow, John D., 1998. Impossibility: The Limits of Science and the Science of limits, pages 8-19, 100-107, 208, 221-228. Oxford University Press(UK) .

Baumslag, Benjamin and Bruce Chandler (1968). Group Theory, pages 107-115, 158-166. McGraw Hill Schaum’s Outline Series. New York ,(USA)

Boyer, Carl B. (1949). The History of the Calculus and its Conceptual Development, pages 33, 291. Dover. New York,USA.

Cayley, A. (1889). A theorem on trees. Quart. J. Math. 23 376-378.

Cohen, Daniel I.A. (1978). Basic Techniques of Combinatorial Theory, pages 13-18, 38, 235,154-157. John Wiley & Sons, New York (USA).

Cordeau, Jean-Francois. (2006). A Branch-and-Cut Algorithm for the Dial-a-Ride Problem. Vol. 54. No. 3, May-June 2006, pp. 573-586.

Coxeter, H.S.M.(1973). Regular Polytopes, pages 118-121. Dover, New York (USA).

Davis, Martin. 1982. Computability and Unsolvability, pages 69 - 70, 199 - 200. Dover, New York (USA).

Deo, Narsingh (1974). Graph Theory with Applications to Engineering and Computer Science, pages 1-11, 52 - 57 , 112 - 135 , 314 - 316. Prentice Hall, Englewood Cliffs (USA).

Duchenne,E., G. Laporte, F. Semet. (2007). The Undirected m-Peripatetic Salesman Problem: Polyhedral Results and New Algorithms. Vol. 55, No. 5, September-October 2007, pp. 949-965.

Ege, Seyhan N. 1984. Organic Chemistry, pages 12-13, 21, 558. D.C. Health and Co. Lexington, USA.

Rothlauf, F. (2009). On Optimal Solutions for the Optimal Communication Spanning Tree Problem. Operations Research, Vol 57, No. 2. March-April, pp.413-425.

Freifelder, David (1985). Essentials of Molecular Biology, pages 17, 47-59. Jones and Bartlett Publishers. Boston, USA.

Gass, Saul I. 1969. Linear Programming Methods and Applications , page 32-33,49-88. McGraw-Hill Kogakusha, Ltd (London).

Grattan-Guinnes, I. Editor (1980). History and Phylosopy of Logic, pages 219, 238-239. Volume I. Abacus Press, UK.

Hillier, F.S. and G. J. Lieberman (1990). Introduction to Operations Research, pages 29-43,59-76.Fifth edition. McGra Hill. New York,USA.

Hocking, John G. and Gail S. Young. 1961. Topology, pages 1-3, 193-199, 203-213. Dover Publication 0-486-65676-4. New York.

Kasner, Edward and James R. Newman. 1989. Mathematics and the Imagination, pages 48 – 49, 265, 276. Microsoft Press, Redmond (USA).

Körner, Stephan. 1968. The Phylosophy of Mathematics: An Introductory Essay, pages 187-191. Dover Publication 0-486-25048-2. New York.

Lawler, E. L. And J. K. Lenstra, A.H.G. Rinnooy Kan and D. B. Shmoys (Editors). 1985. The Travelling Salesman Problem, page 2-3, 17 - 36, 290 - 320, 380 - 392, 443 - 448. John Wiley & Sons, New York.

Lipschutz, Seymour. 1965. General Topology, Pages 1-8 , 48-51, 66-72, 87-90, 180-193 .Graw Hill Schaum’s Outline Series

Masterton, W. L., and E. J. Slowinski. 1969. Chemical Principles, second edition, pages 113-117, 152-153. W.B. Saunders Co. London.

Morrison , Robert T. and Robert N. Boyd. (1973). Organic Chemistry, page 1-11, 23, 36, 154-163, 177-185,219, 262-267, 440-448. Allyn and Bacon Inc. New York.

Nemhauser, G. L. And L. A. Wosley. 1988. Integer and combinatorial Optimization, pages 83 - 43, 469-495, 659 - 719. John Wiley & Sons. New York, USA .

Nyirenda (a), L.D. (1991). Algebraic Network Protection and Restoration Logistics, pages 21-58, 109-127 Ph.D. dissertation, University of California Irvine, Irvine, California, USA. University Microfilm International Dissertation Information Service, order number 9129104. Ann Arbor, USA.

Nyirenda (b), Lemba D. (2004). “Travelling Salesman Problem Solution as a D-Cut Simplex Protein Folding Problem”., VLIR Inter-Discilinary Research. University of Zambia, School of Engineering, Department of Electrical & Electronic Engineering, Lusaka, Zambia. February 2004. Pages 1-17. (For UNZA Science & Technology Journal).

Nyirenda (c), L.D. (2005). TSP Solvability and Computability Research Monograph, UNZA, Department of Electrical & Electronic Engineering, School of Engineering, Lusaka, Zambia. January 2005. Pages 1-34.

Nyirenda (d), Lemba D. and Roland Schinzinger. (2003). “Traveling Salesman Problem Linear Path Spanning Tree Simplex Algorithm”. Presented August 2003 at EURO XVI International Meeting, Istanmbul, Turkey.

Nyirenda (e), Lemba D. and Roland Schinzinger. (2009). “Dedekind-Cut TSP Linear D1-Path Cumulated Corner Poit Polarization Revised Simplex Method”. The Zambian Engineer (Journal of the Engineeing Institution of Zambia) Volume 42, No. 1, January-February 2009, pp.30-37.

Nyirenda (f), Lemba D. , “TSP – STP Dedekind-Cut Network Choice Functions”. Lifelines Operations Research Paper. University of Zambia, School of Engineering, Department of Electrical & Electronic Engineering, Lusaka, Zambia. February 2000.

Nyirenda (g), L.D. “Dedekind-Cut Network Pathset Submodular Division

TSP Simplex Algorithm”. Paper presented at the Joint EURO XV - INFORMS XXXIV International Meeting, July 14-17 ,1997 Barcelona ,Spain.

Nyirenda (h), L. D., “Algebraic Solution of 1856 Travelling Salesman Problem”. Lifelines Networks Research, Department of Electrical & Computer Engineering,University of California at Irvine, USA. Pages 1-5. January 1992.

Nyirenda (i), L.D. and R. Schinzinger, “P- and NP-Completeness of the

Travelling Salesman Problem”. ORSA/TIMS Bulletin Number 34, San Francisco, p.70-TB9.1,1992.

Nyirenda (k), L.D. and R. Schinzinger, “Algebraic Network Solvability: Composition Series Constructive Proof and Topological Groupoids”. SIAM Discrete Mathematics Conference, Atlanta, Georgia, June 1990.

Parker, R. Gary and Ronald L. Rardin. 1988. Discrete Optimization, pages 1 - 10, 23 - 48, 93-94.Academic Press, Boston (USA).

Phillips, Don T. and Alberto Garcia-Diaz. 1981. Fundamentals of Network analysis, pages 3-15,97-109. Prentice Hall. New York , USA.

Preparata, F. P. and M. I. Shamos (1985). Computational Geometry, pages 1-20. Springer-Verlag. New York, USA.

Diestel, Reinhard (1990). Graph Decompositions: A study in Infinite Graph Theory, pages xii-xiii, 5-47. Oxford University Press. New York, USA.

Rosen, H. Kenneth (Editor In Chief). 1999. Handbook of Discrete and Combinatorial Mathematics, pages 107-109, 676-687, 692-702, 959-962. CRC Press (London).

Royden, H.L. (1988). Real Analysis, pages 5-11, 72-74, 137-147, 171-189, 253-254. Mcmillan Publishing Company. New York, USA. (Royden, et al., 1988)

Sommer Halder R. and S. C. van Westrhenen. 1988. The Theory of Computability: Programs, machines, effectiveness and Feasibility, pages 337-353 , 394-417 .Addison-Wesley Publishers Ltd. (UK).

Suppess, Patrick. 1972. Axiomatic Set Theory, pages 68 - 69, 74 - 75, 239 - 240, 250 - 253. Dover, New York (USA).

Tuma, Jan J. 1989. Handbook of Numerical Calculations in Engineering, pages 16, 27, 36, 40, 98. McGraw Hill, New York (USA).