• Recall that time complexity (also known as running time) is a property of a Turing machine (property of a program)
• Time complexity is a function from N → N , which for input 𝑛 gives as output the longest time the program takes on an input of size (or length) 𝑛
• The time complexity of a program is a different function from the function being computed by the program
• A function (or a problem) can be computed (solved) by different algorithms. These different algorithms may have different time complexities
• In practice, when we say that a problem or a function (instead of a program) has time complexity 𝑂(𝑓(𝑛)), then we mean that the fastest program to solve that problem has time complexity 𝑂(𝑓(𝑛))
Other things to remember
• For a function 𝑔, 𝑂(𝑔 𝑛 ) can be seen as a class of functions, which is the collection of all the functions 𝑓: N → N such that 𝑓(𝑛) = 𝑂(𝑔(𝑛))
• A language is a set of strings (a subset of Σ∗). If we think of Σ∗as N, then a language is a set of natural numbers
• We often refer to a language (or a set of natural numbers) by the word problem, or more precisely, the phrase decision problem.
• A decision problem 𝐴 is equivalent to computing 𝐼 : Σ∗ → {0,1} 𝐴
Code Help, Add WeChat: cstutorcs
What is a decision problem?
What is a solution of a decision problem?
A decision problem is a set (a subset of some “bigger” decidable set such as Σ∗, N, we will see more examples)
A solution is a computer program that computes the indicator function of that set
Decision Problems in this course
When working with decision problems, we will need to figure out a suitable Σ∗. In other words, a suitable universe in which the elements of the decision problem live
For example, 𝑥 2
Consider the following decision problem: 𝑦 ∈ N : 𝑥 + 𝑦 = 1
A suitable universe would be N2
Another suitable (but less suitable universe) would be Z2
In some informal sense, what makes a universe suitable are two things:
1. The universe is easily decidable (or let’s say, as easy as it can be)
2. The universe makes building and computing the decider function as easy as possible
Why do we need the universe to be decidable?
Well, by definition it is computably equivalent to N, so it has to be decidable
From a practical perspective, when you define the decider by writing a program (or building a machine), you want it to be able to know which inputs work for it (so that it always halts).
A decider must halt on all elements in the universe
Example: The PATH problem
Given a directed graph 𝐺 and two nodes (vertices) 𝑠, 𝑡 in 𝐺. Consider
the following question: Is there a path from s to t ? The decision problem:
𝑃𝐴𝑇𝐻={ 𝐺,𝑠,𝑡 :𝐺isadirectedgraphthathasadirectedpathfrom𝑠to𝑡}
A suitable universe:
{ 𝐺,𝑠,𝑡 :𝐺isadirectedgraphand𝑠,𝑡areverticesin𝐺}
Solving PATH
To solve PATH based on the suggested universe, we need a program that answers the following question:
Is there vertices 𝑣 , 𝑣 , … 𝑣 such that the edges 12𝑛
(𝑠,𝑣 ),(𝑣 ,𝑣 ),…(𝑣 ,𝑡) are edges in 𝐺? 112𝑛
The program will assume that any given input is
(Graph, vertex in the graph, vertex in the graph)
In a real application, your program may be given any possible computer string as an input, and the first thing your program should do is to check if the given input has the form (Graph, vertex in the graph, vertex in the graph)
Example input
Let’s say you decided to represent graphs in Python as:
{‘A’: {‘B’}, ‘B’: {‘D’, ‘C’}, ‘C’: {‘D’}, ‘E’: {‘F’}, ‘F’: {‘C’}}
Then let’s say you wrote a function to decide PATH. A sensible user of that function should on purpose only try an input like:
( {‘A’: {‘B’}, ‘B’: {‘D’, ‘C’}, ‘E’: {‘F’}} , ‘B’ , ‘D’ )
But let’s say the user inputs (Home, dog, cat),
or inputs ({‘A’: {‘B’}, ‘B’: {‘D’, ‘C’}, ‘E’: {‘F’}}, ‘J’ , ‘K’ ), then your program should tell “Invalid input” (which a language like Python automatically does in many cases)
浙大学霸代写 加微信 cstutorcs
Theorem: PATH ∈ 𝑃
To prove this theorem, we need to show that PATH has a polynomial time decider
This can be broken down into two steps:
1. Prove the existence of a suitable universe which is polynomial time decidable
2. Prove that the indicator function for PATH based on that suitable universe is polynomial time computable
Equivalently, prove the existence of a polynomial time program which decides PATH and knows which inputs are valid/invalid
What we have here doesn’t only apply to PATH, but to any problem solvable in polynomial time.
The size of an input
Let’s take as an example an input like (Graph, vertex, vertex). It is not hard to see that the size of such an input is
𝑂(number of vertices in the graph) or 𝑂(number of edges in the graph)
This is why the time complexity for a program that solves PATH is expected to be expressed as 𝑂 𝑔 |𝑉| where 𝑉 stands for the set of vertices in the input graph, or as 𝑂 𝑔 |𝐸| where 𝐸 is the set of edges, or as 𝑂 𝑔 𝑉 , |𝐸|
Computer Science Tutoring
A polynomial time algorithm for PATH exists
Input: a binary string
1. Decide if it corresponds to a triple (directed graph, vertex1, vertex2) 2. Decide if vertex1 and vertex2 are in the graph?
3. Decide if there is a path from vertex1 to vertex2 in the graph?
There exists polynomial time algorithms for each of 1 and 2. Steps 1 and 2 check if an input is valid. The really interesting part is step 3
An algorithm for step 3
1. Mark the vertex s (perhaps save it in a specific array called Marked) 2. Repeat the following until no additional vertices are marked:
Scan all the edges in the graph, and if any starts at a marked vertex but ends at an unmarked vertex, then mark the end vertex
3.If t gets marked, accept (there is a path). Otherwise, reject (no path).
Or if the graph is implemented nicely (like we did on slide 9), use BFS. As you know, implementing an algorithm depends on the data structures used. An algorithm has to be polynomial time, either as a known fact, or you prove it.
Determinism vs Nondeterminism
The TMs we know so far, from a given state and a symbol, we know exactly what the next state will be (deterministic)
A new kind of TMs is what we call nondeterministic machines (NTMs). In this new kind, several choices may exist for the next state at any point.
The difference between the two kinds is in the transition function (or relation):
• Transitionfunction(Deterministic)
• Transition relation (Nondeterministic)
𝛿: 𝑄 × Γ → 𝑄 × Γ × {𝐿, 𝑅} 𝛿⊆(𝑄×Γ)×(𝑄×Γ× 𝐿,𝑅)
In some references, instead of using a transition relation, 𝛿 is defined to be a function from: 𝑄×Γ→𝑃(𝑄×Γ× 𝐿,𝑅 )
𝑞 𝑏𝑞 1𝑅 01
𝑞 1𝑞 𝑏𝑅 11
𝑞 𝑏𝑞 𝑏𝑅 11
𝑞 𝑏𝑞 𝑏𝑅 10
Visualize the possible ways to run this program as tree branches
Halting in NTMs
When does an NTM halt on a given input? If one branch halts (existential halting)? If all branches halt (universal halting)? Is the output the same from all the branches that halt?
We will adopt existential halting. I like it because it keeps the halting problem σ0 instead of 010
making it ς2 (while presenting the lecture, I mistakenly rushed and said it is ς1 ) It is common to allow NTM branches to give different outputs
For the purpose of decision problems, the NTMs we will be working with are deciders: 1. they halt for any given input on all branches
2. they output accept/reject
For your peace of mind, consider the discussion in red is just there for culture
Natural Questions
Question 1: when does a decider NTM accept ? Answer: If at least one branch accepts
Question 2: what is time complexity for a decider NTM?
Answer: We say a decider NTM has time complexity (running time) 𝑓(𝑛) if 𝑓(𝑛) is the maximum number of steps to reach a halt over all branches over all inputs of size 𝑛
TMs vs NTMs
Clearly every TM is also an NTM (special case by definition)
Exercise: show that every decider NTM can be simulated by a decider TM. Observe how time complexity changes.
The class NP
(nondeterministic polynomial time)
= {𝐿: 𝐿 is a language decidable by an 𝑂 𝑓 𝑛 nondeterministic TM}
𝑁𝑃 = ራ 𝑁𝑇𝐼𝑀𝐸(𝑛𝑘) 𝑘∈N