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:

Definition: \(\Prob{median of an array}\) problem

Instance: A sequence of integers.

Question: What is the median of the values in the sequence (“no” if the sequence is empty)?

And the following decision version is in the class \(\Poly\):

Definition: \(\Prob{median of an array (a decision version)}\) problem

Instance: A sequence of integers and an integer \(k\).

Question: Is the median of the values in the sequence \(k\) or more?

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: \(\Prob{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: \(\Prob{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: \(\MSTDEC\) problem

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: \(\Prob{Minimum Steiner tree (decision version)}\) problem

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?