Discrete Structure.docx

DISCRETE STRUCTURE PRESENTED TO Sir . ABDULLAH PRESENTED BY ROLLNO: 17631556-055 ROLLNO: 17631556-005 ROLLNO: 17631556-016

P VS NP PROBLEM Computational problem In theoretical computer science, a mathematical object representing that computers might be able to solve.

a computational problem is a collection of questions

Because of there large time complexity.

Time complexity The number of (machine) instructions which a program executes during its running time is called its time complexity in computer science. This number depends primarily on the size of the program's input.

Example: for(int i=1; i<=n; i++)

{ for(int j=1; i<=n; i++) { cout<<“time complexity”;}} time complexity=n*n=n2;

Turing machine: • A Turing machine is a mathematical model of computation that defines an abstract machine, which manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, given any computer algorithm, a Turing machine capable of simulating that algorithm's logic can be constructed.

Millennium problems • P versus NP problem. • Hodge conjecture. • Poincaré conjecture (solved) • Riemann hypothesis. • Yang–Mills existence and mass gap. • Navier–Stokes existence and smoothness. • Birch and Swinnerton-Dyer conjecture.

P-Problem P stands for polynomial time Polynomial time means that the complexity of the algorithm is O(n^k), where n is the size of your data (e. g. number of elements in a list to be sorted), and k is a constant. P is a complexity class that represents the set of all decision problems that can be solved in polynomial time. That is, given an instance of the problem, the answer yes or no can be decided in polynomial time. Example Given a connected graph G, can its vertices be colored using two colors so that no edge is monochromatic? Algorithm: start with an arbitrary vertex, color it red and all of its neighbour blue and continue. Stop when you run out of vertices or

you are forced to make an edge have both of its endpoints be the same color. Complexity is time measured in the number of operations it would take, as a function of the number of data items. Operation is whatever makes sense as a basic operation for a particular task. For sorting the basic operation is a comparison. For matrix multiplication the basic operation is multiplication of two numbers.

Np stands for (non deterministic polynomial time) NP is the set of decision problems solvable in polynomial time by a non-deterministic Turing machine . Decision problems cannot be solved in polynomial time but can only be verified Now first we understand what are decision problems ??? decision problem : problems where the answer is either YES or NO. We can identify a decision problem with the subset of inputs that have answer YES. This simplifies notation and allows us to write x∈Q in place of Q(x)=YES and x∉Q in place of Q(x)=NO. • Sometimes we do not know any efficient way of finding the answer to a decision problem, however if someone tells us the answer and gives us a proof we can efficiently verify that the

answer is correct by checking the proof to see if it is a valid proof. This is the idea behind the complexity class NP… • Here is an example of a problem which we do not know how to solve efficiently but we can efficiently verify proofs: • Partition Input: a finite set of natural numbers S, Question: is it possible to partition S into two sets A and B such that the sum of the numbers in A is equal to the sum of number in B • If the proof is too long it is not really useful, it can take too long to just read the proof let alone check if it is valid. We want the time required for verification to be reasonable in the size of the original input, not the size of the given proof! This means what we really want is not arbitrary long proofs but short proofs. • if I give you S and ask you if we can partition it into two sets such that their sums are equal, you do not know any efficient algorithm to solve it. You will probably try all possible ways of partitioning the numbers into two sets until you find a partition where the sums are equal or until you have tried all possible partitions and none has worked. If any of them worked you would say YES, otherwise you would say NO. • But there are exponentially many possible partitions so it will take a lot of time. However if I give you two sets A and B, you can easily check if the sums are equal and if A and B is a partition of S. Note that we can compute sums efficiently. • The amazing thing is that the same situation applies to many other natural problems that we want to solve: we can efficiently verify if

a given short proof is valid, but we do not know any efficient way of finding the answer. This is the motivation why the complexity class NP is extremely interesting • NP problems can not be solved in polynomial time but can only be verified by a nondeterministic turing machine that "guesses" each step correctly. • Why isn't this the case for Mario ,chess and go ?? Can't such a machine just guess the right way, for example, for Mario to go at each gadget thus rendering the problem in NP

NP-Hard A problem is NP-Hard if every problem in NP can polynomial reduce to it.

NP Complete Problem A problem is NP Complete I it is in NP and NP-Hard. OR The class of NP Complete problem is intersection of NP and NP-Hard. NP Complete problem is decision problem and NP-Hard problem is optimization problem. If problem A is a decision problem and problem B is optimizing problem then A B All NP Complete problem is NP-Hard but all NP-Hard problem is not NP Complete.

SAT Problem Boolean satisfiabillity problem abbreivated as SAT Problem . this problem is detremine of there exist a set of boolean variable which satisfy a boolean formula. We determine the value in the form of 0 or1,true or false , yes or no. Input: A boolean formula Output: Find for which combinition of variable ,the boolean formula become TRUE

NP Completeness of SAT • SAT is NP • The reduction function F is define as: • Name each wire coming out of each gate is Xout • Introduce a clause for each gate with k input iff (X1in

X2in

……

Xnin )

• Take AND on all these clause on all Xout

• We have to show that if C-SAT is NP Complete then SAT is also NP Complete • A circuit C is satisfiable iff the formula off(C) is satisfiable • If C is satisfiable then there exist an assignment to its input wire that result output in 1. • Therefore there exist an assignment to all intermediate I/p o/p wire , resulting in satisfying assignment to the formula f(C). • If f(C) is satisfiable then any satisfying assignment result in a satisfying assignment to circuit C, by restricting it to variable for input wire. • The reduction function f can be computed in polynomial time.

P = NP This one is the most famous problem in computer science, and one of the most important outstanding questions in the mathematical sciences. In fact, the Clay Institute is offering one million dollars for a solution to the problem (Stephen Cook's writeup on the Clay website is quite good). It's clear that P is a subset of NP. The open question is whether or not NP problems have deterministic polynomial time solutions. It is largely believed that they do not. Here is an outstanding recent article on the latest (and the importance) of the P = NP problem

P ≠ NP IF in any case p is not equal to Np .then we assume that there is some problem exist in world that are not solveable.