\(\newcommand{\Java}{\href{http://java.com/en/}{Java}}\)
\(\newcommand{\Python}{\href{https://www.python.org/}{Python}}\)
\(\newcommand{\CPP}{\href{http://www.cplusplus.com/}{C++}}\)
\(\newcommand{\ST}[1]{{\Blue{\textsf{#1}}}}\)
\(\newcommand{\PseudoCode}[1]{{\color{blue}\textsf{#1}}}\)
\(%\newcommand{\subheading}[1]{\textbf{\large\color{aaltodgreen}#1}}\)
\(\newcommand{\subheading}[1]{\large{\usebeamercolor[fg]{frametitle} #1}}\)
\(\newcommand{\Blue}[1]{{\color{flagblue}#1}}\)
\(\newcommand{\Red}[1]{{\color{aaltored}#1}}\)
\(\newcommand{\Emph}[1]{\emph{\color{flagblue}#1}}\)
\(\newcommand{\Engl}[1]{({\em engl.}\ #1)}\)
\(\newcommand{\Pointer}{\raisebox{-1ex}{\huge\ding{43}}\ }\)
\(\newcommand{\Set}[1]{\{#1\}}\)
\(\newcommand{\Setdef}[2]{\{{#1}\mid{#2}\}}\)
\(\newcommand{\PSet}[1]{\mathcal{P}(#1)}\)
\(\newcommand{\Card}[1]{{\vert{#1}\vert}}\)
\(\newcommand{\Tuple}[1]{(#1)}\)
\(\newcommand{\Implies}{\Rightarrow}\)
\(\newcommand{\Reals}{\mathbb{R}}\)
\(\newcommand{\Seq}[1]{(#1)}\)
\(\newcommand{\Arr}[1]{[#1]}\)
\(\newcommand{\Floor}[1]{{\lfloor{#1}\rfloor}}\)
\(\newcommand{\Ceil}[1]{{\lceil{#1}\rceil}}\)
\(\newcommand{\Path}[1]{(#1)}\)
\(%\newcommand{\Lg}{\lg}\)
\(\newcommand{\Lg}{\log_2}\)
\(\newcommand{\BigOh}{O}\)
\(\newcommand{\Oh}[1]{\BigOh(#1)}\)
\(\newcommand{\todo}[1]{\Red{\textbf{TO DO: #1}}}\)
\(\newcommand{\NULL}{\textsf{null}}\)
\(\newcommand{\Insert}{\ensuremath{\textsc{insert}}}\)
\(\newcommand{\Search}{\ensuremath{\textsc{search}}}\)
\(\newcommand{\Delete}{\ensuremath{\textsc{delete}}}\)
\(\newcommand{\Remove}{\ensuremath{\textsc{remove}}}\)
\(\newcommand{\Parent}[1]{\mathop{parent}(#1)}\)
\(\newcommand{\ALengthOf}[1]{{#1}.\textit{length}}\)
\(\newcommand{\TRootOf}[1]{{#1}.\textit{root}}\)
\(\newcommand{\TLChildOf}[1]{{#1}.\textit{leftChild}}\)
\(\newcommand{\TRChildOf}[1]{{#1}.\textit{rightChild}}\)
\(\newcommand{\TNode}{x}\)
\(\newcommand{\TNodeI}{y}\)
\(\newcommand{\TKeyOf}[1]{{#1}.\textit{key}}\)
\(\newcommand{\PEnqueue}[2]{{#1}.\textsf{enqueue}(#2)}\)
\(\newcommand{\PDequeue}[1]{{#1}.\textsf{dequeue}()}\)
\(\newcommand{\Def}{\mathrel{:=}}\)
\(\newcommand{\Eq}{\mathrel{=}}\)
\(\newcommand{\Asgn}{\mathrel{\leftarrow}}\)
\(%\newcommand{\Asgn}{\mathrel{:=}}\)
\(%\)
\(% Heaps\)
\(%\)
\(\newcommand{\Downheap}{\textsc{downheap}}\)
\(\newcommand{\Upheap}{\textsc{upheap}}\)
\(\newcommand{\Makeheap}{\textsc{makeheap}}\)
\(%\)
\(% Dynamic sets\)
\(%\)
\(\newcommand{\SInsert}[1]{\textsc{insert}(#1)}\)
\(\newcommand{\SSearch}[1]{\textsc{search}(#1)}\)
\(\newcommand{\SDelete}[1]{\textsc{delete}(#1)}\)
\(\newcommand{\SMin}{\textsc{min}()}\)
\(\newcommand{\SMax}{\textsc{max}()}\)
\(\newcommand{\SPredecessor}[1]{\textsc{predecessor}(#1)}\)
\(\newcommand{\SSuccessor}[1]{\textsc{successor}(#1)}\)
\(%\)
\(% Union-find\)
\(%\)
\(\newcommand{\UFMS}[1]{\textsc{make-set}(#1)}\)
\(\newcommand{\UFFS}[1]{\textsc{find-set}(#1)}\)
\(\newcommand{\UFCompress}[1]{\textsc{find-and-compress}(#1)}\)
\(\newcommand{\UFUnion}[2]{\textsc{union}(#1,#2)}\)
\(%\)
\(% Graphs\)
\(%\)
\(\newcommand{\Verts}{V}\)
\(\newcommand{\Vtx}{v}\)
\(\newcommand{\VtxA}{v_1}\)
\(\newcommand{\VtxB}{v_2}\)
\(\newcommand{\VertsA}{V_\textup{A}}\)
\(\newcommand{\VertsB}{V_\textup{B}}\)
\(\newcommand{\Edges}{E}\)
\(\newcommand{\Edge}{e}\)
\(\newcommand{\NofV}{\Card{V}}\)
\(\newcommand{\NofE}{\Card{E}}\)
\(\newcommand{\Graph}{G}\)
\(\newcommand{\SCC}{C}\)
\(\newcommand{\GraphSCC}{G^\text{SCC}}\)
\(\newcommand{\VertsSCC}{V^\text{SCC}}\)
\(\newcommand{\EdgesSCC}{E^\text{SCC}}\)
\(\newcommand{\GraphT}{G^\text{T}}\)
\(%\newcommand{\VertsT}{V^\textup{T}}\)
\(\newcommand{\EdgesT}{E^\text{T}}\)
\(%\)
\(% NP-completeness etc\)
\(%\)
\(\newcommand{\Poly}{\textbf{P}}\)
\(\newcommand{\NP}{\textbf{NP}}\)
\(\newcommand{\PSPACE}{\textbf{PSPACE}}\)
\(\newcommand{\EXPTIME}{\textbf{EXPTIME}}\)
\(\newcommand{\Prob}[1]{\textsf{#1}}\)
\(\newcommand{\SUBSETSUM}{\Prob{subset-sum}}\)
\(\newcommand{\MST}{\Prob{minimum spanning tree}}\)
\(\newcommand{\MSTDEC}{\Prob{minimum spanning tree (decision version)}}\)
\(\newcommand{\ISET}{\Prob{independent set}}\)
\(\newcommand{\SAT}{\Prob{sat}}\)
\(\newcommand{\SATT}{\Prob{3-cnf-sat}}\)
\(\newcommand{\VarsOf}[1]{\mathop{vars}(#1)}\)
\(\newcommand{\TA}{\tau}\)
\(\newcommand{\Eval}[2]{\mathop{eval}_{#1}(#2)}\)
\(\newcommand{\Booleans}{\mathbb{B}}\)
\(\newcommand{\UWeights}{w}\)
\(\newcommand{\False}{\textbf{false}}\)
\(\newcommand{\True}{\textbf{true}}\)
\(\newcommand{\SSDP}{\textrm{hasSubset}}\)
\(\newcommand{\SUD}[3]{x_{#1,#2,#3}}\)
\(\newcommand{\SUDHints}{H}\)
Polynomial-time solvable problems
A problem is polynomial-time solvable if
there is an algorithm that solves the problem in time \(\Oh{n^c}\)
for some constant \(c\), where \(n\) is the length of the input instance in bits (or, equivalently, in bytes).
We consider such problems to be efficiently solvable,
or tractable.
If a problem is not tractable, then it is intractable.
The class of all decision problems that can be solved in polynomial time is denoted by \(\Poly\).
Note
Polynomial-time algorithms involve algorithms with running
times such as \(\Theta(n^{100})\).
Such algorithms can hardly be considered as “efficient”.
But such running times do not occur often and once a polynomial-time
algorithm is found, it is in many cases further improved to run in
polynomial-time with a quite small polynomial degree.
Based on the sorting algorithms round, we know how to sort an
array of \(n\) elements in time \(\Oh{n \Lg n}\).
Thus the following function problem can be solved in polynomial time:
And the following decision version is in the class \(\Poly\):
From the graph rounds we know how to efficiently compute
shortest paths between the vertices in a graph.
Thus the following problem belongs to \(\Poly\):
Definition: The shortest path problem
Instance: an undirected graph \(\Graph=\Tuple{\Verts,\Edges}\), two vertices \(\Vtx,\Vtx' \in \Verts\), and an integer \(k\).
Question: Is there a path of length \(k\) or less from \(\Vtx\) to \(\Vtx'\)?
However, for the longest simple path problem we do not know any polynomial-time algorithms:
Definition: The longest simple path problem
Instance: an undirected graph \(\Graph=\Tuple{\Verts,\Edges}\), two vertices \(\Vtx,\Vtx' \in \Verts\), and an integer \(k\).
Question: Is there a simple path of length \(k\) or more from \(\Vtx\) to \(\Vtx'\)?
Similarly, we know how to compute minimum spanning trees efficiently
and the following problem is thus in \(\Poly\):
Definition: The minimum spanning tree problem (decision version)
Instance: A connected edge-weighted and undirected graph \(G=\Tuple{\Verts,\Edges,\UWeights}\) and an integer \(k\).
Question: Does the graph have a spanning tree of weight \(k\) or less?
But when not all the vertices have to be included in the tree,
we do not know any algorithm that would solve all the instances efficiently:
Definition: The minimum Steiner tree problem (decision version)
Instance: A connected edge-weighted and undirected graph \(\Graph=\Tuple{\Verts,\Edges,\UWeights}\), a set \(S \subseteq \Verts\), and an integer \(k\).
Question: Does the graph have a tree that spans all the vertices in \(S\) and has weight \(k\) or less?