34.1 Polynomial Time

Solvable problems

Polynomial time algorithms generally regarded as tractable solutions to problems.

1. Lower-order polynomial time algorithms most common.Θ(n¹⁰⁰) superpolynomial time but intractable, often the case that a lower-order polynomial time algorithm will be discovered.
2. Polynomial time solution in one computing model can often be solved in polynomial time in another model. Increasing the number of processors does not significantly change the order of the solution.
3. A solution using two polynomial time algorithms, where the output of one is the input of the other, is still polynomial time.

Example: Closure property under addition, multiplication and composition. Total time(A & B) = Time(A) + Time(B)

Abstract Problems

Example

A Path problem instance is the input: a triple (G, u, v), where G is a directed graph and u and v are vertices in the graph.

At right: G =( V, E ), u=s, v=x.

 

Path's I - is the set of all problem instances of the Path type.  I = {i₁, i₂, ... }, where each i_j is of the form (G, u, v).

(G,s,x) represents one instance of I.

 

Path's S - is the set of all Path solutions.  S = {s₁, s₂, ... }, where each s_j is of the form <v₁, v₂,  ..., s_n >, a sequence of vertices in the graph, or <|> if no path exists.

For the graph, one instance of S is the path <s,y,z,x>.

For the graph, one instance not of S is the path <x, s>.

 

The Path Abstract Problem (PAP):

• Is a relation PAP | I x S such that members of the relation are tuples of the form (i_j, s_k) and appear in the relation only when solution s_k is a solution to problem instance i_j.
  • Example: i_j=(G, s, x), s_k=<s,y,z,x> so (i_j, s_k) ∈ PAP, that is an (instance, solution) tuple.
• (i_j, s_k) does not appear in PAP if s_k is not a solution to problem instance i_j 
•  i_j may appear in PAP more than once since there may be more than one solution to problem instance i_j

Question: Give another (i_j, s_k) ∈ PAP.

Example

The Path abstract decision problem is a four-tuple (G, u, v, k), where G is a graph and u and v are vertices in the graph, and k is the upper limit on the number of edges in the path from u to v.

Path's I - is the set of all problem instances of the Path type.  I = {i₁, i₂, ... }, where each i_j is of the form (G, u, v, k) 

Path's S - is the set of all Path solutions.  S = {0, 1}

The Path Abstract Decision Problem (PADP):

• Is a relation PADP | I X S such that members of the relation are tuples of the form (i_j, s_k) and ∀j i_j ∈ I then (i_j, 0) ∈ PADP or (i_j, 1) ∈ PADP, where s_k = 0 if there does not exist a path from u to v of at most k edges and s_k = 1 if a path does exists with at most k edges.

  Examples:

  • i_j=(G, s, z, 20), s_k=1
  • i_j=(G, s, z, 1), s_k=0

Summary

To develop a method for showing a problem is NP-complete, we need a general representation of problems (abstract) and that have a yes/no answer (decision).

 

Encodings

• An encoding of a set S of abstract objects is a mapping e from S to the set of binary strings.

  Example: Natural numbers to binary strings 0 → 0, 1 → 1, 2 → 10, 3 → 11, 4 → 100, ...

• An algorithm solves an encoding of a problem, not the problem itself.

  Example: The encoding of the graph could be from abstract V = {s, x, y, z} to binary V={0, 1, 10, 11}

• An encoding of an abstract problem instance is called a concrete problem.

• An algorithm that solves an abstract decision problem takes a concrete encoding of an abstract problem instance

• running time - If an algorithm can produce a solution to a concrete problem instance i in O(T(n)) time, then it is said to solve the problem instance i of length n = |i| in O(T(n)) time.

• polynomial-time solvable - if there exists an algorithm to solve a concrete problem in O(n^k) time for some constant k, the problem is said to be polynomial-time solvable

• standard encoding - encodings that are done in a reasonable and concise fashion so that the encoding does not affect the algorithm's complexity

• complexity class P - is the set of concrete decision problems that are polynomial-time solvable

Example

Given the graph G, provide an encoding for a PATH decision problem xi = (G, u, v, k), where: G is the graph, u is the source vertex, v is the target vertex, k is an integer specifying the maximum allowable length of a path from u to v. G = (V, E) V = {r, s, t, u, v, w, x, y} E = {(r, s) (r, v) (s, w) (w, t) (w, x) (t, u) (t, x) (u, y) (u, x)} x1 = (G, r, y, 5) = ((V, E), r, y, 5)      = (({r, s, t, u, v, w, x, y},            {(r, s) (r, v) (s, w) (w, t) (w, x) (t, u) (t, x) (u, y) (u, x)} ),               r, y, 5) =                  (          (          {         r            ,           e(x1) = 0101000 0101000 1111011 1110010 0101100 s           ,           t          ,             u         , 1110011 0101100 1110100 0101100 1110101 0101100 1110110 0101100 1110111 1110111 0101100 1111000 0101100 1111001 1111101 0101100 1111011 0101000 1110010 0101100 1110011 0101001 0101000 1110010 0101100 1110110 0101001 0101000 1110011 0101100 1110111 0101001 0101000 1110111 0101100 1110100 0101001 0101000 1110111 0101100 1111000 0101001 0101000 1110100 0101100 1110101 0101001 0101000 1110100 0101100 1111000 0101001 0101000 1110101 0101100 1111001 0101001 0101000 1110101 0101100 1111000 0101001 1111101 0101001 0101100 1110010 0101100 1111001 0101100 0110101 0101001    ,         y           ,           5          )

Use ASCII for the vertex labels, and the special symbols: symbol ASCII 7-bit r 114 1110010 s 115 1110011 t 116 1110100 u 117 1110101 v 118 1110110 w 119 1110111 x 120 1111000 y 121 1111001 { 123 1111011 } 125 1111101 ( 40 0101000 ) 41 0101001 , 44 0101100 5 53 0110101

Formal Language Framework

• ∑ - an alphabet that is a finite set of symbols
• L - a language over  ∑ is any set of strings made up of the symbols from ∑
• The empty string is denoted by: ε
• The empty language is denoted by: |
• ∑^* - the language of all strings over ∑

  Example:

  • ∑ = {0, 1}
  • L_odd = {1, 11, 101, 111, 1001, ...} is the language of binary representations of odd numbers.
  • L_prime = {10, 11, 101, 111, 1011, ...} is the language of binary representations of prime numbers.
  • ∑^* = {ε, 0, 1, 00, 01, 10, 11, 000, ... }

  Question: What is {0, 1}^*? You can think of this in terms of EBNF from programming languages.

   

• Operations on languages (a language is a set)
  • Union
    • Example: L_odd | L_prime = {1, 10, 11, 101, 111, 1001, 1011, ...}
      
  • Intersection
    • Example: L_odd ∩ L_prime = {11, 101, 111, 1011, ...}
      
  • Complement of L defined as L_odd = ∑^* - L_odd

    Question: What is L_odd for the above example?

  • Concatenation of two languages L₁, L₂ is L = {x₁x₂ : x₁ ∈ L₁ and x₂ ∈ L₂}
    • Example:

      L₁ = {0, 1}

      L₂ = {11, 111}

      L = {011, 0111, 111, 1111}

  • L^k - is the language obtained by concatenating L to itself k times
  • L^* - is the closure or Kleene star is L^* = {ε} U {L¹} U {L²} U {L³} U ...

    Question: What is L₁² for above example?

     

Decision problem Q

∑^*, the set of problem instances, that Q produce a 1 (yes)

Q as a language L over ∑ = {0, 1} where:

L = {x ∈ ∑^* :  Q(x) = 1}

Says that L is the language over all instances for which decision problem Q produces 1 (yes).

Example: The PATHL language for the PATH decision problem is then: PATHL  = {<G, u, v, k> : G=(V, E) is an undirected graph u, v ∈ V k ≥ 0 an integer and there exists a path from u to v in G consisting of at most k edges } PATHL defines the set of instances for which the decision problem PATH produces 1 (yes). Example: <G, s, x, 3> is one instance of PATHL where: V= {s,y,z,x} E = {(s,x),(x,y),(y,x),(y,z),(s,y)} G = (V,  E)

Question:

•  Is <G, s, x, 1> one instance of PATH_L?

•  Is <G, s, z, 1> one instance of PATH_L?

 

Relation Between Decision Problems and Algorithms

accepts - algorithm A accepts as input a string x ∈ {0, 1}^* if A(x) produces 1 as output

rejects - algorithm A rejects as input a string x ∈ {0, 1}^* if A(x) = 0 as output

accepted - for language L = {x ∈ {0, 1}^* : A(x) = 1} then language L is said to be accepted by algorithm A, L is the set of strings A accepts.

decided - algorithm A decides language L if ∀x ∈ L, A(x) = 1 and ∀x ⊆ L, A(x) = 0

If ∀x ∈ L, A(x) = 1 and ∃x ⊆ L that A(x) fails to reject (e.g., runs forever) then A does not decide L.

Example: If the PATH decision problem loops infinitely on any instance not in the PATH_L language, then the PATH decision problem does not decide the PATH_L language.

accepted in polynomial time - algorithm A accepts language L in polynomial time if L is accepted by A and if ∃ k ≥ 0 such that ∀x ∈ L, A accepts x in O(n^k) time.

decided in polynomial time - algorithm A decides language L in polynomial time if L is decided by A and if ∃ k ≥ 0 such that ∀x ∈ L, A correctly decides whether x ∈ L in O(n^k) time.

Example of a language: PATHL language for PATH decision problem: PATHL = {<G, u, v, k>  : G=(V, E) is an directed graph u, v ∈ V k ≥ 0 an integer and there exists a path from u to v in G consisting of at most k edges } accepts - algorithm A accepts as input a string x if A(x) produces 1 as output accepted - for language L, ∀x ∈ L, A(x) = 1 then language L is said to be accepted by algorithm A, L is the set of strings A accepts. rejects - algorithm A rejects as input a string x if A(x) = 0 as output decided - algorithm A decides language L if ∀x ∈ L, A(x) = 1 and ∀x ⊆ L, A(x) = 0

Example of an accepting algorithm: The language PATHL for the PATH decision problem can be accepted in polynomial time by algorithm APATH. APATH works as follows on instance (G, u, v): verifies that G correctly encodes an directed graph verifies that u and v are vertices in G uses Dykstra Algorithm to compute the shortest path from u to v in G compares the number of edges found in the shortest path to k If G correctly encodes an directed graph, and if the number of edges in the shortest path from u to v is less than or equal to k, then APATH outputs a 1 and halts, accepts instance. Otherwise APATH runs forever. Example of a deciding algorithm: APATH works the same as above, but if G correctly encodes a directed graph, and if the number of edges in the shortest path from u to v is less than or equal to k, then APATH outputs a 1 and halts, accepts. Otherwise APATH outputs a 0 and halts, rejects. Question a For the instance of PATHL: V= {s,y,z,x} E = {(s,x),(x,y),(y,x),(y,z),(s,y)} G = (V,  E) Would APATH <G, s, x, 2> accept? reject? decide? Question b What about APATH <G, s, x, 4>

Complexity Classes

• complexity class - a set of languages such that membership of L in the set is determined by a complexity measure (e.g., running time) of an algorithm A that determines whether x ∈ L
• complexity class P -   P = {L | {0, 1}^* : ∃ an algorithm A that decides L in polynomial time}