STUDY OF P=NP

DRAFT

(DOCUMENT UNDER ADVANCED STAGE OF PREPARATION)

A PROBLEM PREDATING THE AGES OF MAN

THE P=NP PROBLEM

(A USER FRIENDLY EXPOSITION FOR GATE/NET /UNDERGRADUATE /INTERMEDIATE/SECONDARY SCHOOL/LITERACY   LEVEL  STUDENTS)

(EXAMINATION ORIENTED MNEMONIC FAIRY TALES & TUTORIAL)

 

 

A. OVERVIEW &  INTRODUCTION

1. INTRODUCTION

[The P=NP problem is considered. It is considered to be the most important open problem in Computer Science and Mathematics. A view point of Algorithms is taken for the treatment of the problem.

Central to the exposition is the development of a dynamic programming  based  Master Construction to show a problem is NP-complete and obtain a software implementation for the same.  Simultaneously   it employs  a  Divide and Conquer strategy with pruning and bounding as heuristics in an overall Branch and Bound Strategy. Every NP-complete problem uses this Master Construction as scaffolding. On this scaffolding attributes and semantic routines are used to realize the NP-complete problem in question. This allows the reducibility among the combinatorial problems to be easily grasped. A few running examples are used for a large collection of NP-complete problems. The running examples are worked out in great  detail to show the reducibility among NP-complete problems.  The aim of the detailed presentation is that any literate person should be able to comprehend the reducibility among the NP-complete problems considered.

For over half a century comprehending and teaching Cooks theorem has proved to be a challenge. Part of the challenge was controlled by trying to describe the concept of NP-completeness using the clique and exact cover problems as central to the concept.

About two decades ago a method employed was to use a simple problem like linear search simulated in detail using models similar to the digital computer with a pidgin structured programming language. This avoids any mention of the Turing Machine to which the software professionals in industry and some others have developed an allergy.

A much simpler model exists. The Turing machine can be used without mentioning or using any of the much-feared and much-hated terminology of Automata Theory. We model the behavior of a college in some of the shady deep interiors and back alleys of the World with the Turing Machine. Hey Presto!! A trivial and crystal clear demonstration of how Cook’s Theorem operates can be explained to secondary school children!! This is shown in the Appendices.

The background developments over the last two centuries of the P=NP problem is  given in the Appendices in the form of a user-friendly  introduction to Metamathematics.

Formal computational models are described in a user friendly way in the Appendices along with the concepts of Order Notation.

The basic foundation 40 practical problems of interest to all Algorithms are also outlined in the Appendices.

The only way to tackle the NP-complete problems for sizes of 100 or so is by massively parallel computing with heuristics. Heuristics depend on the application area and are not considered here. The principles of concurrency are covered in a user-friendly way in the Appendices as they are central to massive parallelism.]

 

2. SCOPE OF THE WORK

[From a catalogued list of 3000 problems  found to possess the resolution of the P=NP question, 60 major, famous problems have been selected. They are uniformly explained using a few running  examples throughout.  Detailed  steps in the implementation of  30   algorithm are given. The application of a Master Construction is discussed for the remaining 30 problems.

Since the P=NP question deals with all areas of human knowledge the exposition is user-friendly and does not assume much mathematical background. Familiarity (or rather literacy) with some Data Structures and Programming is assumed. This is now normally part of any literacy program.

The target audience starts with GATE/NET students and undergraduate syllabi  requirements in Algorithms and The Theory of Computation in the lower tier colleges.  A more ambitious aim is to make the topics part of any adult literacy program.

The aim is to make the problem, its nature and sample 60 problems and relationship comprehendible easily by  intermediate level/secondary school level  students.

Parts of the exposition are for primary and secondary school children. There are pointers to PPTs prepared for the same audience.

Some parts may even be used with kindergarten children. Pointers to free PPTs hosted on the Web are given.]

 

3. THE BACKGROUND OF THE PROBLEM

[From the time of recorded history, mythology and legends some problems have proved to be extremely difficult to solve easily. These are especially true for problems involving combinations.

If a gadget is disassembled how do we put it back together easily? How  can we play Blind Man’s Buff without help? How can we solve crossword puzzles and Sudoku puzzles easily? How can we find our way to our friend’s house easily through a maze of roads? What are the buttons that should be pressed on the PC    should be easily determined.]

4. THE MEANING OF NONDETERMINISM IN COMPUTATION

[In all problems like getting through a maze, there are various choices at many stages as what should be the next step.  We do not know which choice of the next step leads to success.

In nodeterminism we are allowed to duplicate ourselves like a Jinn of the desert. Each copy chooses one choice and all copies aim parallel.

If a copy succeeds we are happy and declare success. We do not count failures provided there is at least one copy that succeeds. If all the copies fail we declare failure.]

5. THE MEANING OF COMPUTATIONAL  COMPLEXITY

[If  in a problem involving combinations of things we do not allow choice but can guess correctly at each step, then we have deterministic behavior.

Some ‘hard’ problems have been identified where deterministic behavior takes an exponential amount of time. If we allow nondeterminism the we can solve the problem ‘easily’. With determinism only problems of the size of about 40 can be solved ‘easily’. The concept of ‘easily’ is formally defined to make the concept precise.

There are problems which are so horrid that even a nondeterministic agent cannot solve them easily. We will not consider these. ] 

6. INTRACTIBILITY MADE SIMPLE

 

[In the problem facing Computer Science and Mathematics we want to know if the so-far identified NP-complete problems can be solved easily.

The 3000 problems identified so far are all related. It is sufficient if one of them can be solved easily.  Then it will turn out that all of them can be solved easily. There is a weighty conjecture to this effect.]

 

 

B. THE PROBLEMS

 

7. SAMPLE  THIRTY  PROBLEMS OF INTEREST

[In this study 30 problems of historical and practical interest have been identified. They have a lot of practical applications. Efficient easy solutions to the problems can result in computational savings of over a trillion dollars]

8. SOLVING THE SAMPLE THIRTY  PROBLEMS NONDETERMINISTICALLY

[If a hypothetical nondeterministic agent like a Jinn or Rakshasa   is given these problems they can be solved efficiently.

Normally, it is easy to show this. It will be shown for all the 30 problems considered.

However, if the nondeterministic ability is removed, the problem takes an exponential amount of time in the general case.]

 

C.  THE SUM OF SUBSETS PROBLEM(#1)

 

9. THE SUM OF SUBSETS PROBLEM AND ITS NONDETERMINISTIC SOLUTION

[The Sum of Subsets problem has been called the easiest had problem. Here  we have some target expenditure to be incurred and have a set of resources which solve our problem in part. A subset of resources that add up to the target is to be determined.]

 

10.                EXAMPLE  SUM OF SUBSETS PROBLEM AND ITS SOLUTION BY THE BRANCH AND BOUND

METHODS

[One way to tackle problems where we have to a subset of the set of resources is the Branch and Bound method. Here the effect of choosing or not choosing a resource is considered. This results in a tree of choices. The leaves of the tree are the solution nodes. Various bounding functions are used to prune the tree as it is traversed. Two types of trees are possible. In a static tree the choices made before the tree is traversed. In a dynamic tree the choices are made as the tree is traversed.]

 

11.                EXAMPLE  SUM OF SUBSETS PROBLEM AND ITS SOLUTION BY THE BACKTRACKING METHOD

[One way of solving the Sum of Subsets problem is to use the strategy of backtracking. This is related to a depth first traversal of a tree. A choice of a path in the tree is made, and in case of failure the search is backed up to the position where the last choice was made. The next alternative choice is made.]

 

12.                EXAMPLE  SUM OF SUBSETS PROBLEM AND ITS SOLUTION BY THE DIVIDE AND CONQUER METHOD—SIMPLE PARTITIONING

[All  methods to solve the Sum of Subsets problem  have turned out to have exponential complexity.  A general solution is demonstrated by a simple Divide and Conquer strategy of splitting the input set of resources into two partitions.

Splitting the input into three partitions turns out to be most probably a heuristic which works sometimes.]

 

13.                EXAMPLE  SUM OF SUBSETS PROBLEM AND ITS SOLUTION BY THE DYNAMIC PROGRAMMING METHOD

[A dynamic programming strategy for solving the sum of subsets problem is considered. Here the input is split into multiple partitions. The partitions are combined using dynamic programming. The method is a heuristic with a worst case exponential time behavior.]

 

14.                EXAMPLE  SUM OF SUBSETS PROBLEM AND ITS SOLUTION BY THE PARTITIONING  METHODS

[Solutions to the Sum of Subsets problem by various partitioning strategies are considered. The partitioning by the ‘blind’ method is also considered.

The strategies are shown to be heuristics that have a worst case exponential complexity.]

D. THE HAMILTONIAN CYCLE PROBLEM(#2)

15.                THE HAMILTONIAN CYCLE PROBLEM AND ITS NONDETERMINISTIC SOLUTION

[The Hamiltonian problem is a venerable combinatorial problem for which no solution simple solution has been found so far over the centuries. It is a graph problem.

Given a graph where the nodes represent our relative’s houses, and the edges represent the existence of a path between two houses. A circuit or cycle is to be determined, starting and ending in some particular house, where all the relatives are visited exactly once.

The problem is easy to solve if nondeterminism is possible. This is demonstrated.]

 

16.                CONVERTING THE  DIRECTED HAMILTONIAN CYCLE PROBLEM TO THE SUM OF SUBSETS PROBLEM

[An example directed  graph is taken and the Hamiltonian cycle problem is encoded as a Sum of subsets problem. This is done for a running example. The encoding can easily be reduced to an instance of the partition problem.]

   

17.                SOLVING THE DIRECTED HAMILTONIAN CYCLE PROBLEM USING THE  SUM OF SUBSETS PROBLEM

[The directed Hamiltonian cycle problem is solved by solving the encoding as a Sum of Subsets problem. This done for a running example. The encoding can easily be reduced to an instance of the partition problem.]

 

 

18.                CONVERTING THE  UNDIRECTED HAMILTONIAN CYCLE PROBLEM TO THE SUM OF SUBSETS PROBLEM

[An example graph is taken and the Hamiltonian cycle problem is encoded as a Sum of Subsets problem.  This is done for a running example. The encoding can easily be reduced to an instance of the partition problem.]

    

19.                SOLVING THE UNDIRECTED HAMILTONIAN CYCLE PROBLEM USING THE  SUM OF SUBSETS PROBLEM

[The undirected Hamiltonian cycle problem is solved using its encoding as a  Sum of Subsets problem. This is done for a running example. The encoding can easily be reduced to an instance of the partition problem.]

 

 

 

 

E.  THE FEEDBACK EDGE SET PROBLEM(#3)

20.                THE FEEDBACK EDGE SET PROBLEM AND ITS NONDETERMINISTIC SOLUTION

[The Feedback Edge set problem is a graph problem. Consider the Indian Railway network modeled as a graph. The nodes are the stations and the edges are trains between stations.

Is there a travel plan of a given fixed number train journeys which will ensure that every station is visited.]

 

21.                CONVERTING THE FEEDBACK EDGE SET PROBLEM TO THE SUM OF SUBSETS PROBLEM

[For a running example it is shown that the Feedback Edge Set problem can be converted to the Sum of Subsets problem. The encoding can easily be reduced to an instance of the partition problem.]

 

22.                SOLVING THE FEEDBACK EDGE SET PROBLEM USING THE SUM OF SUBSETS PROBLEM

[For a running example of a graph it is shown that the Feedback Edge Set problem can be solved by converting it to the Sum of Subsets problem. The encoding can easily be reduced to an instance of the partition problem.]

 

F.  THE VERTEX COVER PROBLEM CONVERTED

 

23.                CONVERTING THE VERTEX COVER PROBLEM TO THE FEEDBACK EDGE SET PROBLEM

[A running example is considered of a graph obtained by converting the  satisfiability  problem to a graph problem and thence to the node cover problem.

The vertex cover problem of the graph is converted to the feedback edge set problem of a graph.]

 

 

G. THE FEEDBACK NODE SET PROBLEM(#4)

24.                THE FEEDBACK NODE SET PROBLEM AND ITS NONDETERMINISTIC SOLUTION

[The feedback node set problem is a graph problem. Given a bus network it can be modeled as a graph. The bus stations are the nodes of the graph. The edges represent bus routes between bus stations.

A subset of a fixed given number of bus stations is to be determined. Every bus route must be taken care of in the subset of bus stations selected.

The problem is solved easily by a nondeterministic computing device. This is demonstrated.]

 

25.                CONVERTING THE FEEDBACK NODESET PROBLEM TO THE SUM OF SUBSETS PROBLEM

[For a running example of a graph the feedback node set problem is converted to the Sum of Subsets problem by a suitable encoding. The encoding can easily be reduced to an instance of the partition problem.]

 

26.                SOLVING THE FEEDBACK NODE SET PROBLEM USING THE SUM OF SUBSETS PROBLEM

[For the running example of a graph the feedback node set problem is solved using the encoding as a Sum of Subsets problem. The encoding can easily be reduced to an instance of the partition problem.]

 

H. THE SATISFIABILITY PROBLEM(#5)

27.                THE SATISFABILITY PROBLEM AND ITS NONDETERMINISTIC SOLUTION

[Given an input set of Boolean variables which can assume the values TRUE or FALSE. Using AND, OR and NOT a CNF form Boolean expression is constructed.

The satisfiability problem asks whether there is an assignment of truth values to the variables which ends up in the Boolean expression being satisfiabe i.e. end up as TRUE when evaluated.

The   problem is easy to solve if a nondeterministic Jinn is around. This is demonstrated.]

 

 

 

I.   THE GRAPH CLIQUE PROBLEM(#6)

28.                THE GRAPH CLIQUE PROBLEM AND ITS NONDETERMINISTIC SOLUTION

[The clique problem is a graph problem. Consider a set of persons forming a network. This can be modeled as a graph. The persons are the nodes and the relationships are the edges.

Is there a gang, called a clique, of a fixed number of persons in the network who are all related to each other?

The problem is easily solved by a Rakshasa or Fairy equipped with the power of nondeterminism.  This is easily demonstrated.]

 

29.                CONVERTING THE SATISFIABILITY PROBLEM TO THE GRAPH CLIQUE PROBLEM

[Two  running example of the satisfiability problem are considered. These are converted to the graph clique problem.]

 

 

30.                CONVERTING THE GRAPH CLIQUE PROBLEM TO THE SUM OF SUBSETS PROBLEM

[A running example of the graph obtained from the conversion from the satisfiabilty problem is considered. The clique problem for this graph is whether a subgraph of a given fixed size or more exists which is a clique.

The graph clique problem is converted to the Sum of Subsets problem. The encoding can easily be reduced to an instance of the partition problem.]

 

31.                SOLVING THE GRAPH CLIQUE PROBLEM WITH ITS ENCODING AS A SUM OF SUBSETS PROBLEM

[To demonstrate the solving of  the graph clique problem, a running example of a graph obtained from a encoding of a Boolean formula is considered. The satisfiabilty problem of the Boolean formula is encoded as a graph clique problem. The graph clique problem is converted to the Sum of Subsets problem  and solved. The encoding can easily be reduced to an instance of the partition problem.]

 

 

J.   THE VERTEX COVER PROBLEM(REVISITED)

32.                THE VERTEX COVER PROBLEM AND ITS NONDETERMINISTIC SOLUTION

[The vertex cover problem is a graph problem. It is also called the node cover problem. Consider an Airline Company. The airports it connects are the nodes of a graph. The edges of the graph model the flights between airports.  It is to be determined if  a subset of given fixed number of airports cover all the flights of the Airline Company. Such a subset is called a vertex/node cover of the graph.

Te vertex cover problem is easy to solve is a nondeterministic Jinn of the desert is around. Its easy solution by a nodeterministic  agent is demonstrated.]

 

 

33.                CONVERTING THE GRAPH CLIQUE PROBLEM TO THE VERTEX COVER PROBLEM

[For a running example of a graph the vertex cover problem is considered.

The graph is obtained starting from a Boolean formula. The satisfiability  problem of the Boolean formula is encoded as a graph clique problem. This is converted to the vertex cover problem of another  graph.

 

34.                CONVERTING THE VERTEX COVER PROBLEM TO THE SUM OF SUBSETS PROBLEM

[A running example is considered. The satsfiability   problem a running example of a propositional formula is considered. This is converted to the clique determination problem of a graph. A new graph is constructed from the old one. The vetex cover problem of the new graph solves the clique determination problem of the old graph. From the new graph a Sum of Subsets problem is created which if solved solves the vertex cover problem of the new graph.]

 

35.                SOLVING THE VERTEX COVER PROBLEM AND ITS  SOLUTION USING THE SUM OF SUBSETS PROBLEM

[From the  running example of the satisfiability of a Boolean formula two graphs are created. The satisfiability problem is related to the vertex cover problem of one of the graphs and the clique determination problem of the other. The vertex cover problem is encoded as the Sum of Subsets problem. This is solved to determine a solution of the node cover problem.] 

 

K. THE DIRECTED HAMILTONIAN CYCLE PROBLEM(#7)

36.                THE DIRECTED HAMILTONIAN CYCLE PROBLEM AND ITS NONDETERMINISTIC SOLUTION

[The nondeterministic solutions to the Hamiltonian problem for directed graphs are revisited.]

 

37.                CONVERTING THE VERTEX COVER PROBLEM TO THE DIRECTED HAMILTONIAN CYCLE PROBLEM

[For a running example the vertex cover problem of a graph is converted to the Hamiltonian cycle problem of a directed graph.

The vertex cover problem of the graph is related to the clique determination problem of another  graph. This clique problem in its turn is related to the satisfiability problem of a Boolean formula.]

 

38.                CONVERTING THE SATISFIABILITY PROBLEM TO THE DIRECTED HAMILTONIAN CYCLE PROBLEM

[For a running example the satisfiability problem of a Boolean formula is converted directly to the Hamiltonian cycle problem for directed graphs. This is converted to the Sum of Subsets problem. The solution of the Sum of Subsets problem solves the Hamiltonian cycle problem and the satisfiability problem.]

 

L.  THE UNDIRECTED HAMILTONIAN CYCLE PROBLEM(#8)

39.                THE UNDIRECTED HAMILTONIAN CYCLE PROBLEM AND ITS NONDETERMINISTIC SOLUTION

[The nondeterministic solutions to the Hamiltonian problem for undirected graphs are revisited.]

 

40.                CONVERTING THE VERTEX COVER PROBLEM TO THE UNDIRECTED HAMILTONIAN CYCLE PROBLEM

[For a running example the vertex cover problem of a graph is converted to the Hamiltonian cycle problem of an undirected graph.

The vertex cover problem of the graph is related to the clique determination problem of another  graph. This clique problem in its turn is related to the satisfiability problem of a Boolean formula.]

 

41.                CONVERTING THE SATISFIABILITY PROBLEM TO THE UNDIRECTED HAMILTONIAN CYCLE PROBLEM

[For a running example the satisfiability problem of a Boolean formula is converted directly to the Hamiltonian cycle problem for undirected graphs. This is converted to the Sum of Subsets problem. The solution of the Sum of Subsets problem solves the Hamiltonian cycle problem and the satisfiability problem. The encoding can easily be reduced to an instance of the partition problem.]

 

 

 

M.       THE TRAVELLING SALESMAN PROBLEM(#9)

42.                THE TRAVELLING SALESMAN PROBLEM AND ITS NONDETERMINISTIC SOLUTION

[The Traveling Salesman Problem is a famous graph problem. Consider a milkman who has to deliver milk to various houses n the town.

His customers’ houses are the nodes of a graph and the edges of the graph represent the milkman traveling from one house to another. Each edge has a weight which represents the cost of traveling from one house to another. 

The Traveling Salesman Problem represents a tour or cycle of the milkman which is a Hamiltonian cycle of least cost.

The problem is easy to solve with a nondeterministic computing device.]

 

43.                CONVERTING THE TRAVELING SALESMAN PROBLEM TO THE SUM OF SUBSETS PROBLEM

[A running example of a graph is given costs to its edges and the Traveling Salesman Problem is converted to the  Sum of Subsets problem. The encoding can easily be reduced to an instance of the partition problem.]

 

44.                SOLVING THE TRAVELING SALESMAN PROBLEM USING THE SUM OF SUBSETS PROBLEM

[The Traveling Salesman Problem is solved by solving the encoding of the same as a Sum of Subsets problem . Two running example is considered. Parallely  two examples are considered which are solved directly using Dynamic Programming  &  Branch and Bound techniques.]

 

45.                SOLVING THE SATISFIABILITY  PROBLEM USING THE SUM OF SUBSETS PROBLEM

[The reducibility among the combinatorial problems considered so far is summarized. The satisfiability problem, the clique determination problem, the vertex cover problem, the feedback edge set problem, the feedback node set problem, the directed/undirected  Hamiltonian cycle problems, the Traveling Salesman problem and the Sum of Subsets problem are related to each other easily.]

 

N. THE 3 CNF SATISFIABILITY PROBLEM(#10)

46.                CONVERTING THE CNF SATISFIABILITY PROBLEM TO THE 3 CNF SATISFIABILITY PROBLEM

[The difficult NP-complete Satisfiability problem is reduced to 3-CNF satisfiability. It is demonstrated that 2-CNF can be solved easily.]

 

O. THE GRAPH COLORING PROBLEM(#11)

47.                THR GRAPH COLORING PROBLEM AND ITS NONDETERMINISTIC SOLUTION

[The famous graph coloring problem is defined. Given a graph can its nodes be assigned colors such that two adjacent nodes do not have the same color? The aim is to find if the graph can be colored by a palette of a fixed number of colors. Determination of the chromatic number is the minimum number of colors needed to color a graph.

The problem can easily be solved by a nondeterministic computing agent. This is demonstrated.]

 

48.                CONVERTING THE 3 CNF SATISFIABILITY PROBLEM TO THE GRAPH COLORING PROBLEM

[A 3 CNF formula is allowed to have only three literals per term. For a running example of a Boolean formula the satisfiability problem is reduced to the satisfiability  of a 3 CNF formula.

This in turn is reduced to an instance of the graph coloring problem.]

 

49.                SOLVING THE GRAPH COLORING PROBLEM USING THE SUM OF SUBSETS PROBLEM

[The graph coloring problem is reduced to the Sum of Subsets problem. This is done for a standard running example of a graph whose graph coloring problem solves the satisfiability  problem of a Boolean formula.

The Sum of Subsets problem is solved to solve the instance of the graph coloring problem. ]

 

 

 

P.  THE SET COVER PROBLEM(#12)

50.                THE SET  COVER PROBLEM AND ITS NONDETERMINISTIC SOLUTION

[The set cover problem is related to sets. Given a family of subsets from a given Universe. Does a subset of the family cover the Universe?

The problem is easy to solve if a nondeterministic agent tackles it. This is demonstrated.]

 

51.                THE SET COVER PROBLEM CONVERTED TO THE SUMOF SUBSETS PROBLEM

[The set cover problem is converted easily to the Sum of Subsets problem. From the running example of a graph the vertex cover problem is converted to the set cover or vice versa. This shows that all the problems considered so far are related, viz. the satisfiability, the clique determination, the vertex cover, the feedback edge set, the feedback node set, the directed/undirected Hamiltonian cycle and the Traveling Salesman problems.]

 

52.                SOLVING THE SETCOVER PROBLEM USING THE SUM OF SUBSETS PROBLEM

[For a running example of a graph the vertex cover problem  is  converted to the set cover problem. This is converted to the Sum of Subsets problem and solved.]

 

 

Q. THE EXACT COVER PROBLEM(#13)

53.                THE EXACT  COVER PROBLEM AND ITS NONDETERMINISTIC SOLUTION

[The exact cover problem is a set problem Given a family of pairwise  disjoint sets a subset of the family must be found that which covers the Universe from which the sets are drawn.

The problem is the ‘Golden Goose’ of NP-complete problems. Most NP-complete problems have a natural formulation as an instance of the Exact Cover problem.

The problem s hard to solve on a deterministic computer but easy to solve on a nondeterministic one.]

 

54.                CONVERTING THE GRAPH COLORING PROBLEM TO THE EXACT COVER PROBLEM & SUMOF SUBSETS PROBLEM

[For a running example the Graph Coloring problem is converted to the Exact Cover problem. This in turn is converted to the Sum of Subsets problem and solved.]

 

R. THE STENIER TREE PROBLEM(#14)

55.                THE STENIER TREE PROBLEM AND ITS NONDETERMINISTIC SOLUTION

[The Stenier  tree problem is a tree problem. Given a weighted tree which has a weight for the edges.  One has to determine a subtree  which includes a subset of a given subset of nodes of the tree.

The problem is difficult to solve deterministically but easy to solve nondeterministically. This is demonstrated.]

 

56.                CONVERTING THE STENIER TREE PROBLEM TO THE SUM OF SUBSETS PROBLEM

[The tree from which the Stenier  tree is to be determined is considered  as a graph. The graph is encoded as a Sum of Subsets problem.]  

 

57.                SOLVING THE STENIER TREE PROBLEM USING THS SUM OF SUBSETS PROBLEM

[The Sum of Subsets encoding  of the Stenier  Tree problem is the fine partitioning  Divide and Conquer algorithm with semantic routines.

This is solved for a running example starting from the satisfiabilility  problem and going through the clique, vertex cover, set cover, feedback edge set, feedback node set, directed/undirected Hamiltonian cycle, Traveling Salesman, graph coloring and the exact cover problems.]

 

 

 

S.  THE KNAPSACK & PARTITION PROBLEMS(#15,#16)

58.                THE PARTITION & KNAPSACKPROBLEMS  & THEIR NONDETERMIMISTIC SOLUTION

[The partition and 0/1 knapsack problems are defined.

The partition problem is a restricted version of the Sum of Subsets problem where the sum of the subsets adds up to half the total sum.

In the 0/1 knapsack problem  the choice of a subset involves a  specified profit. The total profit of a solution to the Sum of Subsets problem is to be minimized.

Both the partition & 0/1 knapsack problems are easy to solve nondeterministically. This is demonstrated.]

 

59.                SOLUTIONS TO THE KNAPSACK PROBLEM USING VARIOUS STRATEGIES

[Solutions to the 01 knapsack problem using the greedy method, the Divide and Conquer strategy, dynamic programming, Branch & Bound, Backtracking and partitioning are covered as PPTs which are hosted on the Web.]

 

60.                CONVERTING THE SUM OF SUBSETS PROBLEM TO THE PARTITION & KNAPSACK PROBLEMS

[The generic solution to the sum of subsets problem with semantics and attributes is used to solve the partition and sum of subsets problems. This is demonstrated for a running example.]

 

 

 

T.  THE THREE DIMENSIONAL MATCHING PROBLEM(#17)

61.                THE 3-DIMENSIONAL MATCHING PROBLEM AND ITS NONDETRMINISTIC SOLUION

[Given three sets can two triples are to be selected. Each triple should have an element from one set. If two triples are taken can we guarantee they will all be different?

This problem is a hard problem which can be solved easily by a nondetermimistivc computing device.]

 

62.                THE 3-DIMENSIONAL MATCHING PROBLEM AND ITS CONVERSION TO THE SUM OF SUSETS PROBLEM

[The three dimensional matching problem is easily converted to the sum of subsets problem. This is done for a running example.]

 

63.                SOLVING THE 3-DIMENSIONAL MATCHING PROBLEM USING THE SUM OF SUBSETS PROBLEM

[The three dimensional matching problem is solved by solving the sum of subsets problem with  three way partitioning.]

 

U. THE 0-1 INTEGER PROGRAMMING PROBLEM(#18)

64.                THE 0-1 INTEGER PROGRAMMING PROBLEM AND ITS NONDETERMINISTIC SOLUTION

[The 0/1 Integer Programming problem is defined and its solution by a nondeterministic agent considered.}

 

65.                CONVERTING THE 0-1 INTEGER PROGRAMMING PROBLEM TO THE SUM OF SUBSETS PROBLEM

[The 0/1 integer programming problem is converted to the generic sum of subsets problem with semantic routines.]

 

66.                SOLVING THE 0-1 INTEGER PROGRAMMING PROBLEM SUING THE SUM OF SUBSETS PROBLEM

[An example of the 0/1 integer programming problem is solved using the generic sum of subsets problem with semantics.]

 

V. THE SET PACKING PROBLEM(#19)

67.                THE SET PACKING PROBLEM AND ITS NONDETERMINISTIC SOLUTION

[The set packing problem is a problem of sets. Given a family of subsets and a  given fixed number  find  disjoint pairs of subsets. The number of subsets forming disjoint pairs should be the fixed number. ]

 

68.                CONVERTING THE SET PACKING PROBLEM TO THE SUM OF SUBSETS PROBLEM

[A running example is taken starting from the satisfiability   problem. This is converted to the clique problem. The clique problem is converted to the Set Packing problem.

The set packing problem is easily converted to the generic Sum of Subsets problem with semantic routines.]

 

69.                SOLVING THE SET PACKING PROBLEM USING THE SUM OF SUBSETS PROBLEM

[The set packing problem for a running example is solved with the generic Sum of Subsets problem with semantic routines.]

 

W.      THE JOB SEQUENCING WITH DEADLINES(#20) PROBLEM

70.                THE JOB SEQUENCING WITH DEADLINES PROBLEM AND ITS NONDETERMINISTIC SOLUTION

[Many scheduling problems are hard problems. The job sequencing with deadlines problem is considered. Given two mechanics the have a steady  stream of orders. An order/job has a deadline and  a profit. The mechanics should choose jobs to maximize their profit and stay within the deadlines.

The problem is a hard one for two mechanics or more. A nondeterministic computer can solve the problem easily. This is demonstrated.]

 

 

71.                CONVERTING THE JOB SEQUENCING WITH DEADLINES PROBLEM TO THE SUM OF SUBSETS PROBLEM

[The job sequencing with deadlines problem is converted to the Sum of Subsets problem. A running  example is taken from the satisfiability   problem. It is converted by stages to the clique, vertex cover, Hamiltonian cycle, traveling salesman problem.  Then it is converted to an instance of job sequencing with deadlines and finally to the generic sum of subsets problem with semantic routines.]

 

72.                SOLVING THE  JOB SEQUENCING WITH DEADLINES PROBLEM USING THE SUM OF SUBSETS PROBLEM

[A running example converted by stages from the satisfiability   problem to the job sequencing with deadlines problem is converted to the generic Sum of Subsets problem with semantic routines. This is solved using  the solution to the generic algorithm.]

 

X. A CODE GENERATION PROBLEM(#21)

73.                THE CODE GENERATION PROBLEM AND ITS NONDETERMINISTIC SOLUTION

[A code generation problem for optimizing code in the presence of common subexpressions   on a single accumulator machine is considered. The problem is shown to be hard. An example is used to illustrate this fact.

A running example is taken. From the satisfiability   problem by a series of reductions an equivalent feedback node set problem is obtained. This is converted to the code generation problem.

It is shown that a nondeterministic computer can solve the problem easily.]

 

74.                CONVERTING THE CODE GENERATION PROBLEM TO THE  FEEDBACK NODE SET PROBLEM

[The code generation problem  is converted to an instance of the feedback node set problem. An example is used to illustrate the conversion.]

 

75.                CONVERTING THE CODE GENERATION PROBLEM TO THE SUM OF SUBSETS PROBLEM

[The code generation problem is converted to the generic  Sum of Subsets problem.  A running example is used to illustrate this.]

 

76.                SOLVING THE CODE GENERATION PROBLEM USING THE SUM OF SUBSETS PROBLEM

[The code generation problem is solved using the generic Sum of Subsets problem.]

 

Y.  THE PARALLEL ASSIGNMENT PROBLEM(#22)

77.                THE PARALLEL ASSIGNMENT PROBLEM AND ITS NONDETRMINISTIC SOLUTION

[The parallel assignment problem in concurrent programming is defined. It is a hard problem. This is shown using a running example. A nondeterministic agent is shown to solve it easily.]

 

78.                CONVERTING THE PARALLEL ASSIGNMENT PROBLEM TO THE SUM OF SUBSETS PROBLEM

[A running example  starting from the satisfiability   problem is converted to the parallel assignment problem. This is then converted to the generic Sum of Subsets problem with semantic routines.]

 

79.                SOLVING THE  PARALLEL ASSIGNMENT PROBLEM USING THE SUM OF SUBSETS PROBLEM

[A running example starting from the satisfiability   problem is used to create an instance of the parallel assignment problem. This is converted to the generic Sum of Subsets problem and solved.]

 

Z.  THE REGISTER ASSIGNMENT PROBLEM(#23)

80.                THE REGISTER ASSIGNMENT PROBLEM AND ITS NONDETERMINISTIC SOLUTION

[The register assignment problem in translator writing is defined. It is shown to be a hard problem.  A nodeterministic   agent is demonstrated to solve it easily.]

 

81.                CONVERTING THE REGISTER ASSIGNMENT PROBLEM TO THE SUM OF SUBSETS PROBLEM

[An example is used to convert a code generation problem to the register assignment problem. This is converted to the graph coloring problem. Then this is converted to the Sum of Subsets problem.]

 

82.                SOLVING THE REGISTER ASSIGNMENT PROBLEM USING THE SUM OF SUBSETS PROBLEM

[The register assignment problem is solved by solving the generic Sum of Subsets problem.]

 

AA.   THE INDEPENDENT SET PROBLEM(#24)

83.                THE INDEPENDENT SET PROBLEM AND ITS NONDETERMINISTIC SOLUTION

[The independent set problem is a graph problem.  Given a graph and a fixed number, find a subset of vertices whose cardinality is of the fixed size. The subset should not have any pair of nodes connected by an edge.

The problem is a hard one and is related to the clique problem. A nondeterministic agent is shown to solve the problem easily.]

 

 

84.                CONVERTING THE INDPENDENT SET PROBLEM TO THE SUM OF SUBSETS PROBLEM

[A running example is taken to convert the satisfiability   problem to the independent set problem in a number of stages. This is finally mapped onto the Sum of Subsets problem with semantic routines.]

85.                SOLVING  THE INDPENDENT SET PROBLEM TO THE SUM OF SUBSETS PROBLEM

 

[The independent set problem is obtained by a series of mappings from an example starting with the satisfiability   problem. This is finally mapped to the Sum of Subsets problem and solved.]

 

BB.   THE HITTING SET PROBLEM(#25)

86.                THE HITTING SET PROBLEM AND ITS NONDETERMINISTIC SOLUTION

[This is a set problem. Given a family of sets a set is to be determined which has exactly one member in common with each member of the family.

The problem of finding a hitting set is hard. The exact cover problem reduces to the hitting set problem.  However a nondeterministic agent can find it easily. This is demonstrated.]

 

87.                SOLVING THE HITTING SET PROBLEM USING THE SUM OF SUBSETS PROBLEM

[The hitting set problem is created from a running example starting with the satisfiability   problem.  The instance of the problem is converted to the generic Sum of Subsets problem and solved with semantic routines.]

 

CC.    THE AND/OR GRAPHS PROBLEM(#26)

88.                THE AND/OR GRAPHS PROBLEM AND THEIR NONDETERMINISTIC SOLUTION

[Work breakdown structures can be modeled by AND/OR graphs. A running example is taken from the satisfiabiity    problem. It is converted to an AND/OR graph.

It is a hard problem which a nondeterministic agent can solve easily.]

 

89.                CONVERTING THE AND/OR GRAPHS  PROBLEM TO THE SUM OF SUBSETS PROBLEM

[Any graph or tree problem can be encoded as a Sum of Subsets problem with the nodes and edges having attributes. The combinations of edges and nodes are handled by semantic routines.

These properties are used to map the AND/OR graph problems  to the generic Sum of Subsets problem.]

 

90.                SOLVING THE AND/OR GRAPHS PROBLEM USING THE SUM OF SUBSETS PROBLEM

[ A running example starting with the satisfiability  problem is taken. This is converted to the AND/OR graph problem. This is mapped to the generic Sum of Subsets problem and solved.]

 

DD.  THE MAXCUT GRAPHS PROBLEM(#27)

 

91.                SOLVING THE MAX CUT PROBLEM OF GRAPHS

[This is a graph problem. Give a weighted graph is there a subset of vertices called a cut? We consider the sum of all weights of edges with one end in the set selected and one without. The Max Cut problem is to find the cut of maximum cost.

For a running example this is reduced to the Sum of Subsets problem with semantic routines. Thus the problem is hard.

A nondeterministic agent is demonstrated  to  solve the problem easily.] 

92.                 SKETCH OF SOLUTIONS OF SOME 30 PROBLEMS

1. The Minimum equivalent graph problem using transitive closure.  (DHC reduces to this.)

2. The DNF tautology problem.

3. Boolean expressions that are not tautologies.

4. Minimum equivalent Boolean form of k literals. (DNF reduces to this.)

5. Hamiltonian path.

6. Minimum finish time nonpreemptive schedule. (Partition reduces to this.)

7. Minimum WMFT nonpreemptive schedule. (Partition reduces to this.)

8. Minimum finish time preemptive flow shop schedule. (Partition reduces to this.)

9. Minimum finish time preemptive job shop schedule. (Partition reduces to this.)

10.        Optimal code generation for leaf dags on an infinite register machine.

11.        Optimal code generation with noncommutative operators.

12.        Minimum cut into equal sized subsets.

13.        Linear package placement problem

14.        Boolean circuit realization with minimum number of gates.

15.        2 SAT with k clauses to be satisfied

16.        Planar Hamiltonian cycle.

17.        Planar node cover.

18.        Unary input partition.

19.        Quadratic programming.

20.        Plant Location.

21.        Concentrator location.

22.        Sub graph isomorphism.

23.        Regular expressions with  + and  .. only. [ Relate to the CNF satisfiability  problem.]

24.        Euclidean traveling salesman problem.

25.        The max clique problem. [Relate to the clique problem. Adjust the semantic routines of the clique problem to find the clique of maximum size.]

26.        The chromatic number problem. [Relate to the graph coloring problem. Find the palette of least size to color the graph.]

27.        The longest path problem. [Reduce to the travelling salesman problem with a unit cost for each edge of a graph.]

 

 

 

 

EE.    THE PHILOSOPHY OF COOK’S THEOREM

93.                THE PHILOSOPHY OF COOK’S THEOREM EXPLAINED

[Cook’s famous theorem  is explained initially informally and then formally.]

 

FF.    COOK’S THEOREM WITH TURING MACHINES

94.                COOK’S THEOREM FOR SECONDARY SCHOOLS USING MODELS SIMILAR TO TURING MACHINES

[The construction in Cook’s theorem is sketched in a user friendly way using Turing machine models. To make the solution user-friendly we simulate a College in the deep interiors of the world.]

 

GG.  COOK’S THEOREM WITH DIGITAL COMPUTERS

95.                COOK’S THEOREM FOR INTERMEDIATE LEVEL STUDENTS USING MODELS SIMILAR TO DIGITAL COMPUTERS

[The construction in Cook’s theorem is explained using models similar to digital computers with a pidgin programming language.

The structured programming constructs and data structures are reduced to single dimensional arrays of integers  and the conditional if statement.

The reduction is to a RASP.

An example of the linear search algorithm is worked out in detail on a 4 bit nondeterministic RASP.]

 

HH.  COOK’S THEOREM WITH ANY COMPUTATIONAL MODEL

96.                COOK’S THEOREM USING THE EXACT COVER PROBLEM

[Cook’s theorem is simulated in detail by using the exact cover problem. A pointer to a PPT on the Web for a detailed simulation is given.]

 

97.                COOK’S THEOREM  USING THE HAMILTONIAN CYCLE PROBLEM

[Cook’s theorem is simulated using IDs of any computation. Thus involves using the Hamiltonian cycle problem.

Alternatively crossing sequences can be used to describe the computation. Since acceptance should be by the shortest path crossing sequences can be use.

The number of crossing sequences is exponential in the vocabulary and states but independent of the input, if we are to keep moving forward.

This gives an exponential time complexity to the computation.

Also it is not clear whether all NP-complete problems can be reduced to each other polynomially  i.e. they are P-isomorphic. There is a weight conjecture to this effect.]

 

98.                COOK’S THEOREM USING THE SUM OF SUBSETS PROBLEM

[Cooks theorem can easily be reduced to the generic  Sum of Subsets problem from the Hamiltonian cycle encoding of the IDs of any computation.

Thus the generic Sum of Subsets construction/generic Partition construction is some sort of a Master Construction for reducibility of problems to  demonstrate  NP-completeness.]

 

II.      CONCLUSION

 

99.                CONCLUSION

[About 60 problems of the 3000 catalogued so far have been considered here. The Web gives details of the other problems.

The Master Construction used is to map the NP-complete problem to the generic Sum of Subsets problem with attributes and semantic routines. Alternatively the mapping is to a generic partition problem  with attributes and semantic routines added as necessary.

The method has been uniformly followed above and can be generalized and used for all NP-complete problems.]

                II. REFERENCES

100.           REFERENCES

1. The Design and Analysis of Computer Algorithms, Aho, Hopcroft & Ullman, 1974, Addison-Wesley.

2. Fundamentals of Computer Algorithms, Horowitz & Sahni, 1976, Galgotia Publications.

 

JJ.      APPENDIX

 

KK.   THE PRINCIPLES OF CONCURRENT PROGRAMMING

 

[The only way to tackle NP-complete problems for sizes of 100 is to use massively parallel computing.  This combined with heuristics related to particular problem domains is what is to be used.

The principles of concurrency are explained in a user friendly way. They are synchronization, mutual exclusion, critical region, semaphores, monitors, busy-wait, deadlock, message passing and broadcasting.

The concept of the producer consumer problem can be used effectively in combining computations with reuse in the handling of NP-complete problems.]

 

 

LL.     APPENDIX I: THE CHOMSKY HIERARCHY DEMYSTIFIED

[A user friendly exposition of the Chomsky hierarchy.]

 

MM.                APPENDIX II: METAMATHEMATICS DEMYSTIFIED

[The background of the P=NP problem in its relation to Mathematics, Computer Science & Computation.]

 

NN.  APPENDIX III:ORDER NOTATION DEMYSTIFIED

[A user-friendly introduction to Order Notation.]

 

OO.  APPENDIX IV: INTACTIBILITY THROUGH FAIRY TALES—PART I

[A user friendly explanation of some NP-complete problems for children.]

 

PP.    APPENDIX V: INTRACTIBILITY TROUGH FAIRY TALES ---PART II

[A user friendly explanation of some NP-complete problems for children.]

 

QQ.  APPENDIX VI: INTRACTIBILITY THROUGH FAIRY TALES---PART III

[A user friendly explanation of some NP-complete problems for children.]

 

RR.   APPENDIX VII:INTRACTIBILITY THROUGH FAIRY TALES----PART IV

[A user friendly explanation of some NP-complete problems for children.]

 

SS.    APPENDIX VII: INTRACTIBILITY THROUGH FAIRY TALES---PART  V

[A user friendly explanation of some NP-complete problems for children.]

 

TT.    APPENDIX VIII:THE CORE TWO SCORE PROBLEMS OF ALGORITHMS—PART  I

[Problems related to Sets.]

 

UU.  APPENDIX  IX:THE CORE TWO SCORE PROBLEMS OF ALGORITHMS—PART  II

[Problems related to Graphs and Trees.]

 

VV.   APPENDIX  X:THE CORE TWO SCORE PROBLEMS OF ALGORITHMS—PART  III

[Problems related to Integers and Polynomials.]

 

WW.              APPENDIX XI:THE CORE TWO SCORE PROBLEMS OF ALGORITHMS—PART  IV

[Problems related to Matrices.]

 

XX.   APPENDIX  XIII:THE CORE TWO SCORE PROBLEMS OF ALGORITHMS—PART  V

[Problems related Strings and Pattern Matching.]

XXI. PICTORIAL SKETCHES

 

 

 

 

 

 

 

 

 

PICTORIAL
SKETCHES
FOLLOW

THE REDUCIBILITY AMONG
COMBINATORIAL PROBLEMS
(SAMPLE OF 30 PROBLEMS)

 

 

 

 

 

PICTORIAL
SKETCHES
FOLLOW

 

 

 

 


                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                           

 

 

 

 

 

 

 

 

 

 

 

 

 

 

THE GENERIC ALGORITHM
FOR SHOWING REDUCIBILITY
AMONG NP-COMPLETE PROBLEMS

 

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                       

 

 

 

 

 

 

 

 

 

 

 

 

 

 

turing.jpgturing.jpgturing.jpgturing.jpgturing.jpg

 
 

 

 

 

 


STARTING
THE POLYNOMIAL TIME BOUNDED
UNIVERSAL COMPUTATION

TURING MACHINES
RASP MACHINES
POST SYSTEMS
MODELS SIMILAR TO DIGITAL COMPUTERS

 

 

 

 


Text Box: THE GENERIC SUM OF SUBSETS AND PARTITION ALGORITHMS                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    

 

                                                                                                                                                             

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

THE REDUCTION
TO
THE GENEREIC ALGORITHM

THE REDUCTION
FROM
THE UNIVERSAL MODELS
OF
COMPUTATION

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


 

FINALISING
THE CONNECTIONS
BETWEEN THE UNIVERSAL
NONDETERMINISTIC DEVICE
AND THE POLYNOMIAL TIME BOUNDED
REDUCIBILITY TO PROBLEMS