Prev: The real deal: Proof of Cook's Theorem in Unary - Thank you Sci.Math for your patience and kindness
Next: Deligne's Finite Fields Riemann Hypothesis uses Math-Induction?? #238; 2nd ed; Correcting Math
From: Jesus Christie on 23 Oct 2009 23:42
34 NP-Completeness
34.1 Polynomial time
From the point of view of language theory,
the set of instances for any decision problem
Q is simply the set Σ*, where Σ = {0,1}. Since
Q is entirely characterized by those problem
instances that produce a 1(yes) answer, we
can view Q as a language L over Σ = {0,1},
where L = {x ∈ Σ* : Q(x) = 1}.
： PATH = {〈G,u,v,k〉 : G = (V,E) is an
undirected graph, u, v ∈ V, k ≥ 0 is an
integer, and there exists a path from u to v in
G consisting of at most k edges}.
28
34 NP-Completeness
34.1 Polynomial time
We say that an algorithm A accepts a string x
∈ {0,1}* if, given input x, the algorithm's
output A(x) is 1. The language accepted by
an algorithm A is the set of strings L = {x ∈
{0,1}* : A(x) = 1}, that is, the set of strings
that the algorithm accepts. An algorithm A
rejects string x if A(x) = 0.
29
34 NP-Completeness
34.1 Polynomial time
A language L is decided by an algorithm A if
every binary string in L is accepted by A and
every binary string not in L is rejected by A.
A language L is accepted in polynomial time
by an algorithm A if it is accepted by A and if
in addition there is a constant k such that for
any length-n string x ∈ L, algorithm A accepts
x in time O(nk).
A language L is decided in polynomial time
by an algorithm A if there is a constant k
such that for any length-n string x ∈ {0,1}*,
the algorithm correctly decides whether x L
in time O(nk).
30
34 NP-Completeness
34.1 Polynomial time
We define a complexity class as a set of
languages, membership in which is
determined by a complexity measure, such
as running time, of an algorithm that
determines whether a given string x belongs
to language L.
We can provide an alternative definition of
the complexity class P: P = {L ⊆ {0,1}* :
there exists an algorithm A that decides L in
polynomial time}.
31
34 NP-Completeness
34.1 Polynomial time
In fact, P is also the class of languages that
can be accepted in polynomial time.
Theorem 34.2 P = {L: L is accepted by a
polynomial-time algorithm}.
32
34 NP-Completeness
Exercises 34.1
34.1-4 Is the dynamic-programming algorithm
for the 0-1 knapsack problem that is asked
for in Exercise 16.2-2 a polynomial-time
algorithm ? Explain your answer.
16.2-2 Give a dynamic-programming solution
to the 0-1 knapsack problem that runs in O(n
W) time, where n is number of items and W is
the maximum weight of items that the thief
can put in his knapsack.
33
34 NP-Completeness
Exercises 34.1
34.1-6 Show that the class P, viewed as a set of
languages, is closed under union,
intersection, concatenation, complement,
and Kleene star. That is, if L1, L2 ∈ P, then L1 ∪
L2 ∈ P, etc.
 | 
Pages: 1
Prev: The real deal: Proof of Cook's Theorem in Unary - Thank you Sci.Math for your patience and kindness
Next: Deligne's Finite Fields Riemann Hypothesis uses Math-Induction?? #238; 2nd ed; Correcting Math