These problems can all be shown complete through very simple reductions
from one of the standard NP-complete problems in the text (mostly from
some variety of 3SAT or HC).
Additional Exercise 1 NAE Max2SAT.
An instance of this problem is given by a collection of 2-literal clauses,
with no variable appearing more than once per clause, and a positive integer
bound K. The question is whether or not there exists a truth
assignment that satisfies at least K of the clauses in NAE fashion,
i.e., such that each satisfied clause has exactly one true and one false
literal.
Additional Exercise 2 Extended Horn Clause Satisfiability.
An instance of this problem is an instance of Satisfiability
where each clause either has two literals or has at most one complemented
literal; the question is whether or not the instance is satisfiable.
A clause with at most one complemented literal is called a Horn clause,
because it can be regarded as an implication: if the clause is
{not(x),y_{1},...,y_{1}}, then it is the
implication x -> y_{1} or ... or y_{n}.
Not that the problem is easily seen to be in P if all of its
clauses have two literals (2SAT) or if all of its
clauses are Horn clauses.
Additional Exercise 3 Set Splitting.
An instance of this problem is given by a set S and a collection
C of subsets of S. The question is whether or not
the set S can be partitioned into two subsets S_{1}
and S_{2} such that every subset in the collection C
has at least one element in S_{1} and one in
S_{2}.
Additional Exercise 4 Feedback Vertex Set.
An instance of this problem is given by a directed graph G=(V,A)
and a positive integer bound K.
The question is where or not there exists a subset V'
of V of size not exceeding K such that every cycle (every
feedback loop) in G includes at least one vertex from V'.
Additional Exercise 5 Feedback Arc Set.
An instance of this problem is given by a directed graph G=(V,A)
and a positive integer bound K.
The question is where or not there exists a subset A'
of A of size not exceeding K such that every cycle (every
feedback loop) in G includes at least one arc from A'.
(Contrast this result with that of Additional Exercise 2.4.)
Additional Exercise 6 Star Matching.
An instance of this problem is given by a graph G=(V,E) and a
positive integer bound K. The question is whether or not
G has a star-matching of size at least K,
where a star-matching is a labeling of the vertices with labels from
the set {0,1} such that each vertex labelled 0 is adjacent
to at least one vertex labelled 1 and the size of such a matching
is the number of vertices labelled 0.
Additional Exercise 7 Negative Directed Simple Path.
An instance of this problem is given by a directed graph G=(V,A),
a weight for each arc chosen from the set {-1,1}, and distinguished
vertices s and t. The question is whether or not there
exists a simple path (i.e., a path that includes each vertex at most once)
from s to t, the total weight of which is negative.
Additional Exercise 8 Fire Truck Placement.
An instance of this problem is given by a graph G=(V,E), a
distinguished vertex v, collection of "fire trucks"
F={f_{1},...,f_{k}} (for k<|V|) with
(positive integer) weight assignment w: F -> N, and positive integer
bound B.
(The value w(f_{i}) denotes the time it takes fire truck
f_{i} to cross a graph edge.)
The question is whether or not there exists an assignment of fire trucks
to graph vertices, loc: F -> V, such that the trucks can all get
to vertex v within B time units, with no two trucks ever
crossing the same edge at the same time.
The edges can be thought of as bridges, which are too fragile to
support more than one truck at a time; the vertices are islands, each of
which -- except for the designated island v -- can serve as the base
for one or more fire trucks; the problem is then to base the trucks so
as to minimize the response time for a fire on island v.
Additional Exercise 9 Partition into Paths of Length 2.
An instance of this problem is given by a graph G=(V,E), with
|V|=3q for some positive integer q. The question is whether
or not there exists a partition of V into q disjoints sets
of 3 vertices each such that, for each 3-subset, at least of the three
possible edges belong to E?
Additional Exercise 10 Comparative Divisibility.
An instance of this problem is given by two sequences of positive
integers, say {a_{i}} and {b_{j}}.
(The sequences may contain multiply repeated values.) The question is
whether or not there exists a positive integer c that
divides evenly more elements of the first sequence than of the second
sequence.
Additional Exercise 11 Graph Grundy Numbering.
An instance of this problem is given by a directed graph G=(V,A).
The question is whether this graph has a Grundy numbering, where such a
numbering is an assignment of non-negative integer labels to vertices
with the following property: if vertex u has arcs to vertices
u_{1},...,u_{k}, then the label of
u is the smallest non-negative integer that differs from the labels
assigned to the vertices u_{1},...,u_{k}.
(In particular, a simple cycle has a Grundy numbering -- of alternating
0s and 1s -- if and only if it has an even number of vertices.)
Additional Exercise 12 Simple Rural Postman.
An instance of this problem is given by a graph G=(V,E),
a designated subset E' of E, and a positive integer
bound K. The question is whether there exists a (not necessarily
simple) cycle in G of length at most K (that is,
with at most K edges) that includes all edges in E'.
The designated edges can be thought of as long side roads that lead
to farmhouses; each such road must be travelled by the rural postman
for deliveries to the farmhouse itself.
Additional Exercise 13 Graph Kernel.
An instance of this problem is given by a directed graph G=(V,A).
The question is whether or not the graph has a kernel, that is, a
subset V' of V such that: (i) V' is an
independent set (no arc exists between any two vertices in the kernel);
and (ii) there is at least one arc from some kernel vertex to any vertex not
in the kernel.
Additional Exercise 14 Partition into Forests.
An instance of this problem is given by graph G=(V,E) and a positive
integer constant K. The wuestion is whether V can
be partitioned into K subsets, call them
V_{1},...,V_{K}, such that each induced
subgraph G_{i}=(V_{i},E_{i}) is a
forest.
Additional Exercise 15 Maximum TR-Matching.
An instance of this problem is given by a graph G=(V,E) and a
positive integer bound K. The question is whether or not the graph
has a TR-matching of size at least K, where a TR-matching on
G is a subset M of E and a labeling of vertices
from the set of labels {source,sink,null} such that:
(i) M is a matching on G, i.e., no two edges in M
share a vertex; (ii) vertices not included in the matching (i.e., that are
not an endpoint of some edge in M) are labeled null;
(iii) each edge in the matching has one endpoint labeled source
and one labeled sink; and (iv) only edges in the matching have
property (iii)---others have endpoints with the same label or with the
null label.
Such a matching allows the testing of edges in a single direction, with a
single transmitter and a single receiver.
Additional Exercise 16 Strong Connectivity Augmentation.
An instance of this problem is given by a directed graph G=(V,A),
a positive integeer weight for each ordered pair of vertices
w: VxV -> N, and a positive integer bound B.
The question is whether or not there exists a set A' of ordered pairs
of distinct vertices from V such that the sum of the weights of
the pairs in A' does not exceed B and such that the
augmented graph G'=(V,A+A') is strongly connected.
Additional Exercise 17 Sequencing to Minimize Tardy Task Weight.
An instance of this problem is given by a set T of tasks,
a positive integer length for each task w: T -> N,
a positive integer weight for each task, w: T -> N,
a positive integer deadline for each task, d: T -> N,
and a bound, K. The question is whether there exists
a single processor schedule s for T such
that the sum of the weights of the tardy tasks (those tasks t
for which s(t)+l(t) > d(t)) does not exceed K?
Additional Exercise 18 Staff Scheduling.
An instance of this problem is given by three positive integers k
(the number of hours of work per scheduling period), m (the number of hours
per scheduling period), and n (the number of workers), a collection
C of m-tuples, each having k 1s and m-k 0s
(the possible worker schedules per scheduling period), and an m-tuple
r of positive integers (the number of workers required at each hour of the
scheduling period).
The question is whether there is a schedule f: C -> {1,2,3,...} (that is,
an assignment of f(c) workers to schedule c such that we
have both sum (over all tuples c in C) f(c) <= n and
sum (over all tuples c in C) f(c)*c >= r?
Additional Exercise 19 Expected Projected Sum.
An instance of this problem is given by a collection C of
n-dimensional binary vectors -- denote vector
v by (v_{1},...,v_{n})
-- and a positive integer bound B. The question is whether the
collection C can be partitioned into three non-empty collections,
C_{1}, C_{2}, and C_{3},
such that the sum over all three collections of the largest projected
sum in each collection does not exceed K -- formally, such that
we have
sum_{i=1}^{3}(max_{1<=j<=n}(sum_{v in Ci} v_{j})) <= B
Additional Exercise 20 Intersection Pattern.
An instance of this problem is given by a symmetric NxN matrix
A=(a_{ij}) with non-negative integer
entries. The question is whether there exists a collection
C={C_{1},...,C_{n}} of sets such that,
for all i,j between 1 and N, we have
a_{ij} = |C_{i} inter C_{j}|
Additional Exercise 21 One-Letter Context-Free Membership.
An instance of this problem is given by a context-free grammar
G=(N,{a},S,P) and a positive integer bound K.
The question is whether the string x=a^{K} can be
generated by G?
Additional Exercise 22 Consecutive Sets.
An instance of this problem is given by an alphabet (a finite set) S,
a collection C of subsets of S, and a positive integer
bound K. The question is whether there exists a string w
of length at most K over the alphabet S such that
every subset in the collection C forms a substring of w
(that is, such that the alphabet symbols of each subset can be ordered so
as to form a substring -- not a subsequence -- of w).
Additional Exercise 23 Path Distinguishers (harder).
An instance of this problem is given by a directed graph G=(V,A),
distinguished vertices s and t of V, and a
positive integer bound K. The question is whether there exists
a subset A' of A of size note exceeding K such
that, for any pair of paths from s to t, there exists
at least one arc in A' that is part of one path but not the other
(and thus distinguishes the two paths).
Other Completeness Proofs
Additional Exercise 24 Context-Free Emptiness.
An instance of this problem is given by a context-free grammar; the
question is whether or not the grammar generates an empty language.
Prove that this problem is P-complete.
Additional Exercise 25 Context-Free Infiniteness.
An instance of this problem is given by a context-free grammar; the
question is whether or not the grammar generates an infinite language.
Prove that this problem is P-complete. (Note that the problem becomes
presumably simpler when useless non-terminals and epsilon productions
are removed.)
Additional Exercise 26 Context-Free Membership.
An instance of this problem is given by a context-free grammar and a
string; the question is whether or not string can be generated by the grammar.
Prove that this problem is P-complete.
Additional Exercise 27 (Restricted) Context-Free Infiniteness.
An instance of this problem is given by a context-free grammar without
epsilon productions and without useless non-terminal; the
question is whether or not the grammar generates an infinite language.
Prove that this problem is NL-complete.
Additional Exercise 28 Strong Connectivity.
An instance of this problem is given by a directed graph; the question
is whether or not the graph is strongly connected. Prove that this
problem is NL-complete.
Additional Exercise 29 Inequivalence of Context-Free Grammars on a One-Symbol Alphabet
(harder).
An instance of this problem is given by two context-free grammars
over the alphabet {a}. The question is whether or not
one grammar generates a string that cannot be generated by the other.
Prove that this problem is complete for Sigma_{2}.
Additional Exercise 30 Disjoint Cycle Covers.
An instance of this problem is given by a directed or undirected graph;
the goal is to find the smallest collection of edge- or vertex-disjoint
cycles such that each vertex of the graph is included in at least one cycle.
Prove that all four versions of this problem are NP-equivalent.
Additional Exercise 31 Pebbling (open-ended and harder).
A pebble game is defined as follows. Given a directed acyclic
graph and a designated vertex, the goal is to place (and remove) pebbles
on the vertices (usually just written "to pebble the vertices") in order
to pebble the designated vertex under the following rules.
Initially, only sources may be pebbled.
If all the parents of a vertex (i.e., all the vertices which are connected
to the given vertex by an arc directed to said vertex) are pebbled, then
the vertex may be pebbled.
A pebble may be removed at any time.
The total number of pebbles present at any time on the graph is not allowed
to exceed a given bound or the total number of moves is limited.
Discuss the time and "pebble" complexity of this problem (both apply since
the game is based on a trade-off between the two.) In particular, consider
the influence of allowing vs. disallowing the re-pebbling of vertices.
Other Problems
Additional Exercise 32
We have seen that PH cannot have complete problems unless it collapses
down to some level -- the argument is the same made for POLYL, except
that POLYL cannot collapse, so that the statement for POLYL, unlike
that for PH, need not be qualified.
We have also seen that PH is a subset of PSPACE -- whether proper or not
remains unknown. However, PSPACE does have complete problems;
what then would be the consequences of the (hypothetical) result
PH=PSPACE?
Additional Exercise 33
We have seen that oracles can be added to our basic Turing machine
model to enhance its capabilities. Armed with some oracle set A
we can define relativized complexity classes L^{A},
NL^{A}, P^{A}, NP^{A}, etc.
Show that there is an oracle A such that we have
P^{A}=NP^{A}.
(Hint: pick a set A complete for a class in which we know
that nondeterminism does not add any power.)