THE NP – PROBLEM

          Two families which constitute the bulk of our practical computational problems and have been central to the theory of computation are:

• The first is a class which contains all of the problems we solve using computers. The problems actually presented to the computer do not require too many computations. In fact, most of the important algorithms computed are somewhere in the O(log n) to O(n³) range. Thus the practical computation resides within polynomial time bounds. This is a class of polynomially solvable problems. P is the set of all decision problems which can be solved in polynomial time by a deterministic Turing machine.
• The second is a class which consists of all the problems is called NP problem. This is a class of nondeterministic polynomially acceptable problems. NP is the set of all decision problems for which the ‘yes’ answers can be verified in polynomial time ( O(n^k) where n is the problem size and k is a constant ) by a non-deterministic Turing machine.

NP-Problem

NP (Non-deterministic Polynomial Time) is one of the most fundamental complexity classes. A decision problem is a collection of questions with yes or no answers that vary only in one parameter.

The NP problems are set of all problems that can be solved in polynomial time using a non-deterministic Turing machine. The algorithm for such a non-deterministic machine consists of two phases, the first consists of a guess about the solution which is generated in a non-deterministic way, and the second consists of a deterministic algorithm that verifies or rejects the guess as a valid solution to the problem.

 NP contains many important problems, the hardest of which are called NP-Complete and NP-Hard. An NP problem X for which it is possible to reduce any other NP problem Y to X in polynomial time ie., Y can be solved quickly if X can be solved quickly. NP-Complete is a class of decision problems and it is a subset of NP. A decision problem is NP-Complete if it is in the set of NP problems and also in the set of NP-Hard problems.

NP-Hard are problems that are at least as hard as the hardest problems in NP. NP-Complete problems are also NP-Hard. NP-Hard problem is a problem for which we cannot prove that a polynomial time solution exists.

Formal definition            

The complexity class NP can be defined using deterministic Turing machines as verifiers. A language L is in NP if and only if there exist polynomials p and q, and a deterministic Turing machine M, such that 

·         For all x and y, the machine M runs in time p(|x|) on input (x,y).

·         For all x in L, there exists a string y of length q(|x|) such that M(x,y) = 1.

·         For all x not in L and all strings y of length q(|x|), M(x,y) = 0.

A decision problem C is NP – complete if

1.      C is in NP, and

2.      Every problem in NP is reducible to C in polynomial time.

A problem that satisfies the 2^nd condition is said to be NP-hard, whether or not it satisfies 1^st condition.

Travelling salesman problem

Imagine you need to visit 5 cities on a sales tour. If we know all the distances then which is the shortest round trip to follow? An obvious solution is to check all possibilities, but this works only for small problems. If a new city is added then it needs to be tried out in every previous combination. So this method takes factorial time: t = n!

LIGHT-UP

            Light Up also called Akari is a binary-determination logic puzzle. Light Up is played on a rectangular grid of white and black cells. The player places light bulbs in white cells such that no two bulbs shine on each other, until the entire grid is lit up. A bulb sends rays of light horizontally and vertically, illuminating its entire row and column unless its light is blocked by a black cell. A black cell may have a number on it from 0 to 4, indicating how many bulbs must be placed adjacent to its four sides. An unnumbered black cell may have any number of light bulbs adjacent to it, or none. Bulbs placed diagonally adjacent to a numbered cell do not contribute to the bulb count.

Solution

Typical starting point in the solution of a Light Up puzzle is to find a black cell with a 4, or a cell with a smaller number that is blocked on one or more sides  and therefore has only one configuration of surrounding bulbs. After this step, other numbered cells may be illuminated on one or more sides, narrowing down the possible bulb configurations around them. A more advanced technique is to look for a cell that is not yet lit, and determine if there is only one possible cell in which a bulb can be placed to light it up.

KAKURO

Kakuro is a kind of logic puzzle that is often referred to as a mathematical transliteration of the crossword. Kakuro puzzles are regular features in many math and logic puzzles. Kakuro puzzle is played in a grid of filled and barred cells, black and white respectively. Puzzles are usually 16×16 in size and they  can vary widely. Apart from the top row and leftmost column which are entirely black, the grid is divided into entries - lines of white cells - by the black cells. The black cells contain a diagonal slash from upper-left to lower-right and a number in one or both halves, such that each horizontal entry has a number in the black half-cell to its immediate left and each vertical entry has a number in the black half-cell immediately above it. These numbers, borrowing crossword terminology, are commonly called clues.

Solution

           One method would be to note where a few squares together share possible values thereby eliminating the possibility that other squares in that sum could have those values. For example, if  two 4-in-two clues cross with a longer sum, then the 1 and 3 in the solution must be in those two squares and those digits cannot be used elsewhere in that sum.

Another useful approach in more complex puzzles is to identify which square a digit goes in by eliminating other locations within the sum. If all of the crossing clues of a sum have many possible values, but can be determined if there is only one square which could have a particular value which the sum in question must have, then whatever other possible values the crossing sum would allow, that intersection must be the isolated value. For example, a 36-in-eight sum must contain all digits except 9. If only one of the squares could take on the value of 2 then that must be the answer for that square.