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?