The following questions are for P and NP Problems. When does a problem belong to
ID: 3770127 • Letter: T
Question
The following questions are for P and NP Problems. When does a problem belong to P-Class and when does it belong to NP Class? Give two P-Class problems, and give two NP-Class problems which no one knows belonging to P-class or not. Give the time complexities of each, respectively. Suppose that A is a problem belong to P-Class and B is a problem belonging to NP-Class. Does A belong to NP-Class? Does B belong to P-Class? Let A be a problem satisfying the following conditions: any problem in NP-Class can be reduced to A in polynomial time, and Ais an NP-complete problem. What class does A belong to?Explanation / Answer
7a)
If there is a fast solution to the search version of a problem then the problem is said to bePolynomial-time, or P for short. If there is a fast solution to the verification version of a problem then the problem is said to be Nondeterministic Polynomial-time, or NP for short.
(or)
The P versus NP problem is to determine whether every language accepted
by some nondeterministic algorithm in polynomial time is also accepted by some
(deterministic) algorithm in polynomial time.
Informally the class P is the class of decision problems solvable by some algorithm
within a number of steps bounded by some fixed polynomial in the length of the
input. Turing was not concerned with the efficiency of his machines, rather his
concern was whether they can simulate arbitrary algorithms given sufficient time. It
turns out, however, Turing machines can generally simulate more efficient computer
models (for example, machines equipped with many tapes or an unbounded random
access memory) by at most squaring or cubing the computation time. Thus P is a
robust class and has equivalent definitions over a large class of computer models.
Here we follow standard practice and define the class P in terms of Turing machines.
Formally the elements of the class P are languages. Let be a finite alphabet
(that is, a finite nonempty set) with at least two elements, and let be the set
of finite strings over . Then a language over is a subset L of . Each Turing
machine M has an associated input alphabet . For each string w in there is
a computation associated with M with input w. (The notions of Turing machine
and computation are defined formally in the appendix.) We say that M accepts w
if this computation terminates in the accepting state. Note that M fails to accept
w either if this computation ends in the rejecting state, or if the computation fails
to terminate. The language accepted by M, denoted L(M), has associated alphabet and is defined by
L(M) = {w 2 | M accepts w}.
We denote by tM(w) the number of steps in the computation of M on input w (see
the appendix). If this computation never halts, then tM(w) = 1. For n 2 N we
denote by TM(n) the worst case run time of M; that is,
TM(n) = max{tM(w) | w 2 n},
where n is the set of all strings over of length n. We say that M runs in
polynomial time if there exists k such that for all n, TM(n) nk + k. Now we
define the class P of languages by
P = {L | L = L(M) for some Turing machine M that runs
in polynomial time}.
The notation NP stands for “nondeterministic polynomial time”, since originally
NP was defined in terms of nondeterministic machines (that is, machines that
have more than one possible move from a given configuration). However, now it is
customary to give an equivalent definition using the notion of a checking relation,
which is simply a binary relation R ×1 for some finite alphabets and 1.
We associate with each such relation R a language LR over [ 1 [ {#} defined
by
LR = {w#y | R(w, y)}
where the symbol # is not in . We say that R is polynomial-time iff LR 2 P.
Now we define the class NP of languages by the condition that a language L
over is in NP iff there is k 2 N and a polynomial-time checking relation R such
that for all w 2 ,
w 2 L () 9y(|y| |w|k and R(w, y)),
where |w| and |y| denote the lengths of w and y, respectively
.
7b)
The set P is defined as the set of all problems that can be
solved in polynomial worse case time
Also known as the polynomial time complexity class –contains problems whose time complexity is O(Nk) for some k
Examples of problems in P: searching, sorting, topological sort, single-source shortest path, Euler circuit, etc.
Example for NP class problem
Recall our friend from last time, the Hamiltonian circuit problem: Find a cycle
that goes through each vertex exactly once
Given a candidate path, can test in linear time if it is a Hamiltonian circuit
NP algorithm for HC:
Guess a candidate path
Check if all vertices are visited exactly once in this candidate path (except start/finish vertex)
Can check in time polynomial in |V|
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.