From CSWiki

CSC 341:Front Door | CSC 341: Cooperative commentary | Sipser:_Chapter_7

Contents 1 P Class 1.1 Summary 1.2 Problems in P 1.2.1 PATH 1.2.2 RELPRIME 1.2.3 Context-free language 1.3 Is this problem in P?

P Class

Summary

This section defines and discusses the problem of class P.

Sipser notes that exponential difference in running time usually occurs when "brute-force search" is used. As previously shown that time complexity of deterministic and non-deterministic Turing machines are at most exponentially different, the polynomial differences are negligable and we can group any problem that is solvable in polynomial time together. Sipser concludes that "all reasonable deterministic computational models are polynomially equivalent."

    Definition 7.12 

    P is the class of languages that are decidable in polynomial time on a deterministic single-tape Turing machine.
    

Problems in P

PATH

(page 260)

This problem asks whether there is a direct path from vertex s to vertex t in a directed graph G.

    Theorem 7.14  

Sipser describes the following Turing machine that solves PATH problem and shows that this algorithm uses polynomial time.

RELPRIME

(page 261)
This problem asks whether two numbers are relatively prime. In other words, is the "greatest common divisor" between the two numbers 1? Sipser solves this problem using Euclidean algorithm.

    Theorem 7.15  

Context-free language

(page 262)
This problem asks if all context-free language is decidable in polynomial time. Sipser builds a Turing machine that does so.

    Theorem 7.16   Every context-free language is a member of P.

Is this problem in P?

The easiest and the most direct way to prove that a problem is in P is to give a polynomial algorithm that solves it. We need usually want to find a algorithm that's better than brute-force search.

---

CSC 341:Front Door | CSC 341: Cooperative commentary | Sipser:_Chapter_7