**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 **

** **

** **

** **

** **