Time Complexity
Co-hosted by Paul
Time Complexity Class
• Let 𝑓: N → R+ be a function. Define the time complexity class 𝑇𝐼𝑀𝐸(𝑓(𝑛)) to be the collection of all languages that are decidable by an 𝑂(𝑓(𝑛)) Turing Machine.
• The class above is a class of languages. Does this seem to cause loss of generality?
• For example, the sorting problem (or function), can it be regarded as a language?
Languages are general enough
• Let’s look at the sorting example. Let Sort be the machine that does the sorting
• Sort is a function that takes a tuple as input and outputs a tuple of the same size
• As we learnt before, a function is a set of ordered pairs. Here, Sort is a subset of N∗ × N∗.
Every function problem can be turned into a decision problem
• Suppose we are given a tuple 𝑥ҧ = (𝑥1,…,𝑥𝑛) and that we want to compute Sort(𝑥ҧ).
• N∗ is c.e., and so we can computably list it, say: (𝑦ത)1, (𝑦ത)2, …
•Andkeepchecking:is(𝑥ҧ,(𝑦ത) )∈Sort?,is(𝑥ҧ,(𝑦ത) )∈Sort?,….untilone
of them is Yes
12
Vice versa
• Every decision problem is a function problem. Why? • Answer: the characteristic function
• Note that the transition from a function problem to a decision problem does not necessarily preserve the TIME complexity class
• Function Problem: Consider a machine Solver which can take an equation as an input (say quadratic equations), and outputs solutions.
• Decision Problem: Given an equation and a value 𝑥, decide whether 𝑥 is a solution for the equation or not.
Sort again (thoughts)
• When we listed (𝑦ത) , (𝑦ത) , … one may chose to do that smartly so
the sorted tuple shows up faster
• For example, we could only list tuple of length n
• With a deeper look, finding a smart way to list the tuples is a process that has its own running time
12
Break
Hope we are comfortable with the fact that complexity theory is developed through decision problems
The class P
• 𝑃 = {𝐿: 𝐿 is a language decidable by some polytime TM}
)𝑘𝑛(𝐸𝑀𝐼𝑇 𝑘ڂ = 𝑃 Note that •
• Why is
ራ 𝑇𝐼𝑀𝐸(𝑛𝑘) = {𝐿: 𝐿 is a language decidable by some polytime TM} 𝑘∈N
How do we prove equality of sets?
:⊆ •
Let L be an arbitrary language from ڂ𝑘∈N 𝑇𝐼𝑀𝐸(𝑛𝑘)
•⊇
Let 𝐿 be an arbitrary language decidable by some polytime TM
The PATH problem
• Given a directed graph G and two nodes 𝑠, 𝑡 in 𝐺. Consider the
following question: Is there a path from s to t ?
• 𝑃𝐴𝑇𝐻 =
{ 𝐺,𝑠,𝑡 :𝐺isadirectedgraphthathasadirectedpathfrom𝑠to𝑡}
• This set (or relation) PATH is an example of what we mean by a problem in the context of complexity
Unfolding PATH
• The question we first asked is equivalent to the following decision
problem
Is 𝐺,𝑠,𝑡 ∈𝑃𝐴𝑇𝐻?
• This question unfolds into:
Is 𝐺 𝑎 directed graph?
Are 𝑠, 𝑡 vertices in 𝐺?
Is there a number 𝑛, and vertices 𝑣 , 𝑣 , … 𝑣 such that the edges 12𝑛
(𝑠,𝑣 ),(𝑣 ,𝑣 ),…(𝑣 ,𝑡)areedges inG? 112𝑛