EECS 376: Foundations of Computer Science
University of Michigan, Winter 2022 Discussion Notes 8 1 The Class P
The class P is the set of languages that can be decided efficiently (in polynomial time with respect to the size of the input to the decider).
Definition 1.1. A language L is efficiently decidable if there exists a decider D that decides the language L efficiently.
Copyright By PowCoder代写 加微信 powcoder
1.1 Example of a language in P
Given a weighted graph G = (V, E), a spanning tree is a subset E′ of edges such that the induced
graph on E′ is connected. Recall this concept from lecture 4. We define the language LSPANNING = {⟨G, k⟩ : G has a spanning tree of size less than k}
Let us prove that LSPANNING is in P. To prove this, we will provide an efficient decider for LSPANNING. Let the decider D be defined as follows:
D = “On input (⟨G, k⟩):
1. Run Kruskal’s algorithm on G to get the Minimum Spanning Tree of G with weight w. 2. If w < k, then accept; else reject.”
Correctness: ⟨G,k⟩ ∈ LSPANNING =⇒ G has a spanning tree of size less than k =⇒ Kruskal’s algorithm will find a MST with weight w < k =⇒ D accepts.
⟨G, k⟩ ∈/ LSPANNING =⇒ G does not have a spanning tree of size less than k =⇒ Kruskal’s algorithm will find a MST with weight w ≥ k =⇒ D rejects.
Time complexity: Kruskal’s algorithm has a runtime of O(|E|log|E|). Therefore, this al- gorithm runs in polynomial time since running Kruskal’s algorithm takes polynomial time with respect to G, and checking if w ≤ k takes linear time with respect to |k|. So, the algorithm is efficient with respect to (G, k).
Example 1.2. Define GCD = {⟨x, y, g⟩ : gcd(x, y) = g}. Consider the following decider:
1: 2: 3: 4:
5: 6: 7: 8: 9:
functiongcd(x,y,g) G=0
ifx