数理解析研究所講究録
第 833 巻 1993 年 11-21$[[$

The Complexity of Selecting Maximal Solutions
Zhi-Zhong Chen

Department of Information Engineering, Mie University, Tsu-shi, Mie 514, Japan.

Seinosuke Toda

Department of Computer Science, University of Electro-Communications,
Chofu-shi, Tokyo 182, Japan.

1

Introduction

Intuitively, a maximization problem is to select a maximal solution for a given input
according to some selection criterion. The maximal independent set problem (MIS) [5]and the minimal unsatisfiability problem (MinUnsat) [11] are two standard examples ofsuch problems. Much work has been devoted to the study of maximization problems[1,2,3,4,5,7,9,11,12]. Most of the previous work has involved studying specific maximization problems and either finding an efficient algorithm (e.g., [5]) or proving the problem
is hard to solve (e.g., [11]). An attractive alternative approach is to study maximization
problems in a general framework and to prove general results.
In this paper, we formalize a maximization problem (MAXP)
as a pair $(D, R)$ ,$D$$R$$D\cross\{0,1\}^{*}arrow$$true$, false} is the instancewhereis the set of instances and:{solution relation. The objective in solving
is to select, given an instance $x\in D$ , amaximal solution, i.e., a binary string such that $R(x, y)$ is true but changing one ormore arbitrary O-bits of to l-bits will change the value of $R(x, y)$ to false. As an
example, consider MIS in our framework. For it, $D$ is the set of all undirected graphs,
and $R(G, b_{1}b_{2}\cdots b_{n})$ is true if and only if has vertices (say, 1, 2,) and { :$b_{i}=1\}$ is an independent set in. Our goal is to demonstrate what factors makeeasy or hard to solve and how the factors influence the complexity of solving . We
are able to find two such factors. One obvious factor is the complexity of $R$ . This canbe seen by comparing MIS with MinUnsat. The instance-solution relation of MIS isdecidable in NC while that of MinUnsat is coNP-complete. Because of this gap, solving
MinUnsat is much harder than solving MIS. In fact, MIS is solvable in NC $[5,7]$ while-hard [11]. The other factor is whether $R$ is hereditary or not,solving MinUnsat is$R$
where is said to be hereditary if and only if for every and , whenever $R(x, w)$ is true,$R(x, w)$ remains true even one or more arbitrary l-bits ofare changed to O-bits. The
instance-solution relation of MIS (also MinUnsat) is hereditary. In [9], Papadimitriou
considered the following problem (MinModel): Given a CNF boolean formula , find asatisfying truth assignment to such that changing one or more arbitrary l-bits of to
O-bits will make no longer satisfy . The instance-solution relation of MinModel is nothereditary but is decidable in NC. Unlike MIS, solving MinModel is obviously NP-hard.
In this paper, we restrict to consider only those MAXP’s whose instance-solution
relation is decidable in NP or $coNP$ . We first consider upper bounds on the complexityof solving such MAXP’s. Let $Q=(D, R)$ be a MAXP. The following give trivial upperbounds: (i) is solvable in FP if $R$ is decidable in and hereditary; (ii)
is solvable
in $NPMV\parallel OptP[O(\log n)]$ if $R$ is decidable in NP; (iii)
is solvable in $FP^{NP}$ if $R$ isdecidable in $coNP$ and hereditary; (iv)
is solvable in
if $R$ is decidable in $coNP$ .
$Q$

$Q$

$y$

$y$

$G$

$n$

$\cdots,$

$i$

$n$

$G$

$Q$

$Q$

$D^{P}$

$w$

$x$

$w$

$\phi$$aarrow$$aarrow$$aarrow$$\phi$$\phi$

$P$

$Q$

$Q$

$Q$

$Q$

$FP^{\Sigma_{2}^{P}}$12
Our main results concerning upper bounds are the following:
is a MAXP whose instance-solution relation is NP decidable. Let(v) Suppose
and a polynomial
be an arbitrary polynomial. Then, there exist a function$\geq
1-2^{-e(|x|)}$ , where
$Pr$
$w)$
$F(x,$[
is a maximal solution of in ]such that for every$w\in\{0,1\}^{p(|x|)}$ is randomly chosen under uniform distribution.
(vi) Suppose is a MAXP whose instance-solution relation is $coNP$ decidable. Let
and a polynomial
be an arbitrary polynomial. Then, there exist a function$Pr$ [ $F(x,$ $w)$ is a maximal solution ofin ] $\geq 1-2^{-e(|x|)}$ , wheresuch that for every$w\in\{0,1\}^{p(|x|)}$ is randomly chosen under uniform distribution.
(v) and (vi) are shown by extending the technique used in [3].
We then show that $NPMV\parallel OptP[O(\log n)]$ is also a lower bound for solving those
MAXP’s whose instance-solution relation is decidable in NP or is decidable in but not
$Q$

$e$

$F\in FP_{||}^{NP}$

$x,$

$p$

$Q$

$x$

$Q$

$e$

$F\in FP_{||}^{\Sigma_{2}^{P}}$

$Q$

$x$

$x,$

$p$

$P$

$\Sigma^{P}$$hreditandtha_{4_{ab1eincoNPbutnothereditary.Combiningtheupperandlower}^{2}}So^{e_{1utionre1ationisdeci}}$bounds, we obtain characterizations of $NPMV\parallel OptP[O(\log n)]$ andvia MAXP’s.
As an important consequence of the characterization of $NPMV\parallel OptP[O(\log n)]$ , we obtain the first natural complete problem for $NPMV\parallel OptP[O(\log n)]$ . The problem (called$X$ -MinModel) is defined as follows: Given a CNF boolean formulaand a subset $X$ ofthe set of variables in , find a satisfying truth assignment to such that changing
one or more arbitrary l-bits of corresponding to variables in $X$ to O-bits will makeno longer satisfy . $X$ -MinModel was first considered by Papadimitriou in [9], and-complete there. However, Papadimitriou
was claimed without a precise proof to belater withdrew his claim and thus left the complexity of $X$ -MinModel open [10]. In [3],we proved that the complexity of $X$ -MinModel is roughly captured by. Now, theresults in this paper give, for the first time, the exact complexity of solving $X$ -MinModel.
We also characterize complexity classes of sets via MAXP’s. The following are shown:(a) $coNP$ is the class of all sets that can be expressed as $L=\{x$ : $f(x)$ is a maximal
solution of in } for some $f\in FP$ and some MAXP whose instance-solution relationis P-decidable.
(b)is the class of all sets that can be expressed as $L=\{x$ : $f(x)$ is a maximal
solution of in } for some $f\in FP$ and some MAXP whose instance-solution relation
is NP-decidable.
(c)is the class of all sets that can be expressed as $L=\{x$ : $f(x)$ is a maximal
solution of in } for some $f\in FP$ and some MAXP whose instance-solution relationis coNP-decidable and hereditary.
(d)is the class of all sets that can be expressed as $L=\{x$ : $f(x)$ is a maximal
solution of in } for some $f\in FP$ and some MAXP whose instance-solution relationis coNP-decidable.
As consequences, we obtain several new natural problems that are-complete for$coNP$ or.
$FP_{||}^{\Sigma_{2}^{P}}$$\phi$$aarrow$$\phi$$\phi$$\vec{a}$$aarrow$$\phi$$\triangle_{2}^{P}$$FP_{||}^{NP}$

$L$

$x$

$Q$

$Q$

$D^{P}$

$L$

$x$

$Q$

$Q$

$D^{P}$

$L$

$x$

$Q$

$Q$

$L$

$\Pi_{2}^{P}$

$x$

$Q$

$Q$

$\leq_{m}^{P}$$D^{P}$

2

Preliminaries

We use $\Sigma=\{0,1\}$ as our alphabet. By a set, we mean a subset of . Similarly, by astring, we mean a string in . We denote by
the length of a finite string . The bits$\Sigma^{*}$$\Sigma^{*}$

$|x|$

$x$

13
, nth
of a finite string with length are indexed from left to right as the 1st, $2nd,$
identify,
usually
we
with
the
set
of all indicesbits, respectively. For a finite stringsuch that the ith bit of is 1. Thus we will often use some set-theoretical notations forfinite strings. A finite string is smaller than another finite string if either $|x|<|y|$. A maximal string in a set of finite strings is a string in thator $|x|=|y|$ andanyother string in .
than
notsmalleristothat is polynomial-time
We assume a one-to-one pairing function fromcomputable and polynomial-time invertible. For strings and , we denote the output of; this notation is extended to denote any k-tuples for $k>2$
the pairing function bydepends only onand .
in a usual manner. W.l. $0.g.$ , we assume that
$A,$$||A||$
denotesdenotes the number of strings in . For a set
For any finite set
denotes the characteristic function of . For a class), andits complement (i.e.,
denoteof sets, $coC$ denotes the class of all sets whose complement is in C. Let
anddenotes the set
the set of all strings with length . For two sets$\cdots$

$n$

$x$

$i$

$x$

$x$

$x$

$y$

$S$

$x\subset y$

$S$

$S$

$\Sigma^{*}\chi\Sigma^{*}$$\Sigma^{*}$

$x$

$y$

$\langle x, y\rangle$$|x|$$|\langle x, y\rangle|$$A$$\Sigma^{*}-L$$|y|$$L,\overline{L}$$L$$\chi_{L}$$C$$\Sigma^{n}$x\in L_{1}\}\cup\{1y :y\in L_{2}\}$$L_{2},$$L_{1}$$n$$\{0x :

$L_{1}\oplus L_{2}$.

to. The symbol is assumed
All functions considered here are ones fromfunctionsand multi-valued functions, but
to be not in . We consider both single-valued
by a function we mean a (partial) single-valued function. For a multi-valued function$G,$ $G(x)$ denotes the set of all possible values ofat . Thus, when $G(x)=\emptyset$ , themulti-valued function is undefined at the argument .
We assume that the reader is familiar with the basic concepts from the theory ofcomputational complexity. Our computational models are variations of standard Turingmachines. A machine is either an acceptor or a transducer, and may be deterministic
while a transducer is denoted
or nondeterministic. An acceptor is denoted by $M$ or
by or . A deterministic (resp., nondeterministic) Turing machine is abbreviated as
DTM (resp., NTM). On a given input, a branch of a (nondeterministic) machine may
halt by entering either a rejecting state or an accepting state. For simplicity, we say thata branch of a machine halts if the branch halts by entering an accepting state. Let $L(M)$denote the set of all strings accepted by $M$ . A transducer computes a string on input
if some branch of on input halts with on the output tape. $T(x)$ denotes thecomputes a function if for all
set of all strings computed by on input . A DTM$T(x)=\emptyset$ if $f(x)$ is undefined, and the unique element of $T(x)$ is $f(x)$ otherwise.
Classes in the first three levels of the polynomial-time hierarchy are denoted in the. Let $D^{P}=$ {: $L_{1}\in NP$ and $L_{2}\in coNP$ }.
usual way: , NP, $coNP,$
FP denotes the class of all functions computed by polynomial-time bounded DTM’s.
be a set.
denotes the class of all functions computed by polynomial-timeLetdenotesbounded deterministic oracle Turing machines (DOTM) with oracle A.
$F$
the class of all functions for which there exists a polynomial-time bounded DOTM
such that , while computing $F(x)$ for a given , prepares all its query strings before
if there exist two
asking them to the oracle . More precisely, a function $F$ is infunctions and in FP such that for all strings $F(x)=g(x, \chi_{A}(y_{1})\cdots\chi_{A}(y_{m}))$ , where$\Sigma^{*}\cup\{\#\}$$\Sigma^{*}$$\#$$\Sigma^{*}$

$G$

$G$

$x$

$x$

$M_{i}$$T$$T_{i}$

$T$

$T$

$x$

$x$

$T$

$y$

$y$

$T$

$x$

$f$

$x\in\Sigma^{*},$$P$$\Sigma_{2}^{P},$$\Pi_{2}^{P}=co\Sigma_{2}^{P}$$L_{1}\cap L_{2}$$FP^{A}$$A$$FP_{||}^{A}$

$T$

$T$

$x$

$A$

$f$

$FP_{||}^{A}$

$x,$

$g$

.

$f(x_{AnNP^{1}metri^{m}\tau_{urimachinei1no^{C}mia1imebo^{A}undedN}^{Frac1assCofsets_{o}FP=\cup FPan_{\#\ovalbox{\tt\small REJECT}_{at}}}})=\langle y,\cdots,y_{c}\rangle.o_{ngsap’ y-t^{A\in C}M\tau_{sucht}^{A\in C}}dFP^{C_{1}}=\cup FP^{A}$on

every input, every branch of outputs a binary number and halts [6].
denotes the class of all (total) integer-valued functions $H$ for which there exist a polynomial and an NP metric Turing machine such that for every $x,$ $H(x)\leq p(|x|)$ and$OptP[O(\log n)]$

$T$

$p$

$T$

14

$H(x)$ equals to the maximum number in $T(x)$ . $NPMV\parallel OptP[O(\log n)]$ denotes the classof all (partial) multi-valued functions for which there exist an NTM and a function$G(x)=T(\langle x, H(x)\rangle)$ .
$H\in OptP[O(\log n)]$ such that for every
A maximization problem (MAXP) is a pair $(D, R)$ , where (i) $D$ is the set of instancesand (ii) $R:D\cross\Sigma^{*}arrow$ { $true$ , false} is the instance-solution relation.
, whenever $R(x, w)$ isis said to be hereditary if for every $x\in D$ and every$w’$$w’\subsetw$. Let $x\in D$ . A stringwith $|w’|=|w|$ andtrue, $R(x, w’)$ is also true for every
$R(x,
w)$
of
is a maximal string inAmaximalsolutionis true.
is called a solution of if
the set of all solutions of . The objective in solving is to compute, given an instance$x\in D$ , a maximal solution of .
Each MAXP $Q=(D, R)$ considered in this paper is required to satisfy the following:(1) $D$ is P-decidable (i.e., decidable in polynomial time), (2) there is a polynomial suchthat for every $x\in D$ and every string , whenever $R(x, w)$ is true, $|w|\leq p(|x|)$ , and (3)is NP-decidable or coNP-decidable.
$T$

$G$

$x,$

$Q$

$w\in\Sigma^{*}$

$R$

$w$

$x$

$x$

$Q$

$x$

$x$

$p$

$w$

$R$

if for every $x\in D,$ $(a)F(x)$ is undefined if
Deflnition 2.1 A function $F$ solves
otherwise. A
and (b) $F(x)$ is a maximal solution of in
has no solution in$(a)G(x)=\emptyset$
$x\in
D,$
if
has
for
no solution in
every
solvesif
multi-valued functionand (b) $G(x)$ is nonempty and each element of $G(x)$ is a maximal solution of inis solvable in a class $H$ of (single-valued or multi-valued) functions if someotherwise.
$H\in H$ solves
.
$Q$

$Q$

$x$

$Q$

$x$

$G$

$Q$

$x$

$Q$

$Q$

$x$

$Q$

$Q$

Definition 2.2 Let be a function, and let be a multi-valued function. Then,(resp., ) is reducible to if there exist two functions $f,$ in FP such that for every ,$f(x)\in D$ and $g(x, w)=F(x)$ (resp., $g(x,$ $w)\in G(x)$ ) for every maximal solutionof$H$$f(x)$ in Q.
of (single-valued or multi-valued) functions if every
is hard for a class$H\in H$ is reducible to Q.
is complete for a class $H$ of (single-valued or multi-valued)is hard for a class of sets if is hard
functions if is solvable in and hard for H.
for the class $\{\chi_{L} : L\in C\}$ .
$F$

$G$

$F$

$G$

$Q$

$x$

$g$

$w$

$Q$

$Q$

Deflnition 2.3 The set $L_{Q}=$ {the decision problem associated with$\langle x,$

3

$C$

$Q$

$Q$

$w\rangle$

$Q$

:

$w$

is a maximal solution of

$Q$

$x$

in

.

$Q$

} is called

Upper bounds

In this section, we show upper bounds on the complexity of solving MAXP’s. The
following proposition shows trivial upper bounds.

Proposition 3.1 Let $Q=(D, R)$ be a MAXP.
(1) If is hereditary and P-decidable, then is solvable in FP.
(2) If is NP-decidable, then is solvable in $NPMV\parallel OptP[O(\log n)]$ .
(3) If is hereditary and coNP-decidable, then is solvable in $FP^{NP}$ .
(4) If is coNP-decidable, then is solvable in
.
$R$

$Q$

$R$

$Q$

$R$

$Q$

$R$

$Q$

$FP^{\Sigma_{2}^{P}}$We next proceed to show two other non-trivial upper bounds. To do this, we needseveral definitions and a known result.

Deflnition 3.1 Let$F$

be a class of functions. Then we define a class$RP\cdot F$

of

15
is in
if for every
multi-valued functions as follows: A multi-valued function
polynomial , there exist a function $F\in F$ and a polynomial such that for every$(a)F(x, w)$ is undefined for all $w\in\{0,1\}^{p(|x|)}$ if $G(x)$ is undefined and (b)string$Pr[F(x, w)\in G(x)\cup\{\#\}]=1$ and $Pr[F(x, w)\in G(x)]\geq 1-2^{-e(|x|)}$ otherwise, where
if for every. Intuitively speaking, is in
is a random string chosen from
$G(x)$
using a function in F.
string , we can randomly pick up an element of$G$$RP\cdot F$

$p$

$e$

$x,$

$w$

$\{0,1\}^{p(|x|)}$$G$$RP\cdot F$$x$

Notation: For $k\geq 1,$ $[1, k]$ denotes the set of all integers with $1\leq i\leq k$ .
$i$Deflnition 3.2 Let be a finite set and let be a positive integer. A weight function
over is a function from the elements of to positive integers. A k-weight function overis a weight function over such that for each $s\in S,$ $f(s)$ is in $[1, k]$ . A random
k-weight function over is a k-weight function over such that for each $s\in S,$ $f(s)$ ischosen uniformly and independently from $[1, k]$ . The weight of a subset $S’$ of under a. Note that for every k-weight function over , the weightweight function isof each subset of under is no more than $k||S||$ and that the empty set is the uniquesubset of with weight .
$S$

$k$

$S$

$S$

$S$

$S$

$f$

$S$

$S$

$f$

$S$

$f$

$S$

$\Sigma_{\iota\in S’}f(s)$

$S$

$f$

$S$

$\emptyset$$0$

Lemma 3.1 [8]. Let be a nonempty family of subsets of a finite set . Then, for
any random k-weight function over with $k\geq 2||S||$ , Pr[There is a unique maximum
weight set in under ]
$S$

$S$

$S$

$f$

$S$

$f$

$\geq\frac{1}{2}$Now we are ready to show the two non-trivial upper bounds. The idea used in the
proof is a generalization of the one used in [3].
Theorem 3.1 Let $Q=(D, R)$ be a MAXP.
(1) If is NP-decidable, then is solvable in
$R$

$Q$

$RP\cdot FP_{||}^{NP}$.

(2) If $R$ is coNP-decidable, then is solvable in
Proof. We only show a proof for (2). (1) can be shown in a similar manner.
(2) We first explain the idea behind the proof. Let
be a polynomial such that for
all $x\in D$ , the length of each solution of is no more than $pQ(|x|)$ . Let be an instanceof . Then, we consider , the family of all solutions of with maximum length. To
find a maximal solution for , we first get a random 2 $p_{Q}(|x|)$ -weight function over$[1, p_{Q}(|x|)]$ . Then, by Lemma 3.1, with probability at least
there is a unique solution
in of maximum weight. To find this unique solution of maximum weight, it suffices
to ask only one round of parallel queries to aoracle set. Since the weight assigned
to each element of $[1, pQ(|x|)]$ is positive, all maximum weight solutions are maximal
solutions (but not necessarily solutions of maximum l-bits). In order to get the highprobability of success, we may perform several copies of this computation in parallel.
We now proceed to give the precise proof. Let
be a polynomial that bounds thelengths of solutions of from above. For convenience, let $n_{x}=p_{Q}(|x|)$ for all $x\in D$ .
Then we define five sets as follows:$L_{R}=$ {: has a solution},$B_{1}=${{ $x,$ : $0\leq i\leq n$ and has a solution of length },: $x\in D,$ $0\leq i\leq n_{x},$ is a-weight function over $[1, n_{x}]$ ,, and has a solution such that $|u|=i$ and is the weight of$Q$$RP\cdot FP_{||}^{\Sigma_{2}^{P}}$$p_{Q}$

$x$

$x$

$S$

$Q$

$x$

$f$

$x$

$\frac{1}{2}$$S$$\Sigma_{2}^{P}$$p_{Q}$

$x$

$x$

$x$

$i\rangle$$B_{2}=\{\langle x, i, f,j\rangle$$0\leq j\leq i2^{1+f^{\log_{2}n_{x}\rceil}}$under },

.

$i$

$x$

$x$

$2^{1+\int\log_{2}n_{x}\rceil}$

$f$

$j$

$u$

$u$

$f$

$B_{3}=\{\langle x,$ $i,$$f,j$ )

: $x\in D,$ $0\leq i\leq n_{x},$

$f$

is a

$2^{1+R\circ g_{2}n_{x}\rceil}$-weight function over$[1, n_{x}]$,16, and has two or more solutions such that $|u|=i$ and is theweight of under }, and-weight function over $[1, n_{x}]$ ,: $x\in D,$ $0\leq i\leq n_{x},$ is a$1\leq k\leq i$ , andhas a solution such that $|u|=i,$ is the weightof under , and the kth bit of is 1}.
, and
are in . Let $B=(((L_{R}\oplus B_{1})\oplus B_{2})\oplus B_{3})\oplus B_{4})$ .
Obviously,
Then,.
Let be an arbitrary polynomial. We define a polynomial as follows: $p(i)=e(i)$ .
$(p_{Q}^{2}(i)+p_{Q}(i))$ . Below, we define a DOTM
which uses as an oracle set. Given an$w\in\{0,1\}^{p(|x|)},$
operates as follows:with $x\in D$ andinput (
$0\leq j\leq i2^{1+R\circ g_{2}n_{x}\rceil}$$2^{1+\int\log_{2}n_{x}\rceil}$$f$$B_{4}=\{\langle x, i, f,j, k\rangle$$0\leq j\leq i2^{1+\beta og_{2}n_{x}\rceil},$

$j$

$u$

$x$

$f$

$u$

$j$

$u$

$x$

$f$

$u$

$u$

$L_{R},$$B_{1},$$B_{2},$$B_{4}$$B_{3}$$\Sigma_{2}^{P}$$B\in\Sigma_{2}^{P}$

$p$

$e$

$B$

$T$

$x,$

$T$

$w\rangle$. If has no
Step 1:checks whether has a solution by asking a query tosolution, then halts by entering a rejecting state.
Step 2: finds , the length of the longest solutions of . This is done by asking the,to the oracle set .
(queries
computesand constructs, from $w,$ -weight functions ,Step 3:$[1,n_{x}]$
as follows:over the set
from such that $|w_{1}|=\cdots=$
Step 3.1: first computes $e(|x|)$ strings$|w_{e(|x|)}|=n_{x}\log_{2}n_{2}$ and the string
prefixis aof (the remaining part of,
into
substrings
is ignored), and then for each $1\leq k\leq e(|x|)$ , it partitions$n^{2}ae+n_{x}\geqn_{x}\log_{2}n_{2}.$). (Note: can do this because
each of length, sets $f_{k}(l)=d_{k,l}+1$ , where
Step 3.2: For each $1\leq k\leq e(|x|)$ and each inrepresentation
binary
is
.
the
whose
is
integercomputes the maximum number
Step 4: For each 1 $\leq k\leq e(|x|),$with. This is done by asking the queries
with $0\leq i\leq n_{x}$ ,$1\leq k\leq e(|x|)$ , and $0\leq j\leq in_{2}$ to the oracle set. (Note: In this step, asks the, and because the machinepossiblequeries of the form (allvaluesofforneeds to prepare all queries independently of each other.)
Step 5: For $1\leq k\leq e(|x|)$ and $1\leq l\leq n_{1},$computes.
$0\leqi\leqn_{x},$$1\leqk\leq
e(|x|)$,
This is done by asking the queries
with$0\leq j\leq in_{2}$ , and $1\leq I\leq i$ to the oracle set. (Note: In this step, asks the queries, and because the machine needsof the form
for all possible values
to prepare all queries independently of each other.)
Step 6: For each $1\leq k\leq e(|x|),$ checks whether. This is doneby asking the queries
with $0\leq i\leq n_{x},$ $1\leq k\leq e(|x|)$ , and $0\leq j\leq in_{2}$ to, then outputs
the oracle set. If for someandhalts; otherwise, outputs the special symbol
and halts.
$T$$L_{R}$

$x$

$x$

$T$

$T$

$x$

$n_{1}$$\langle x, 0\rangle,$$x,$$1\rangle$$\cdots,$$n_{2}=2^{1+[\log_{2}n_{x}\rceil}$$T$$f_{2},$$\cdots,$$B_{1}$$\langle x, n_{x}\rangle$$f_{1}$$n_{2}$$f_{e(|x|)}$$T$$w_{1},$$w$$w_{e(|x|)}$$\cdots,$$w$$w_{1}w_{2}\cdots w_{e(|x|)}$$w$$n_{x}$$w_{k}$$w_{k,n_{x}}$$w_{k,1}$$T$$\log_{2}n_{2}$$d_{k,1}$$T$$[1, n_{x}]$$I$$w_{k,l}$$T$$m_{k}$$\langle x, n_{1}, f_{k}, m_{k}\rangle\in B_{2}$$\langle x, i, f_{k},j\rangle$$T$$B_{2}$$x,$ $i,$ $f_{k},$$i,$$j\rangle$

$k$

$j$

$T$

$a_{k,l}=\chi_{B_{4}}(\langle x, n_{1}, f_{k}, m_{k}, l\rangle)$$\langle x, i, f_{k},j, l\rangle$$T$$B_{4}$$i,$$\langle x, i, f_{k},j, l\rangle$

$k,$

$l$

$j$

$T$

$\langle x, n_{1}, f_{k}, m_{k}\rangle\in B_{3}$$\langle x, i, f_{k},j\rangle$$k,$$B_{3}$$T$$\langle x, n_{1}, f_{k}, m_{k}\rangle\not\in B_{3}$$T$$a_{k,1}a_{k,2}\cdots a_{k,n_{1}}$$\#$Let $F$ denote the function computed by with oracle $B$ . We can easily see that ispolynomial-time bounded and all query strings are prepared independently of each other;
this means that the query strings made by on input (can be realized as parallel
queries to the oracle set $B$ . Thus, $F$ is in.
Let
be a multi-valued function defined by $G(x)=\{F(x, w)$ : $w\in\{0,1\}^{p(|x|)}$ and$F(x, w)$ is $defined$ } $-\{\#\}$ . We show thatsolves and is in. To this end,
we first prove two claims.
$T$

$T$

$T$

$x,$ $w\rangle$$FP^{\Sigma_{2}^{P}}$

$||$

$G$

$G$

Claim 1 Suppose that for some

$k$

$Q$

with $1\leq k\leq e(|x|),$$RP\cdot FP_{||}^{\Sigma_{2}^{P}}$$x$

has a unique solution with

17
output by is aunder . Then, the string
and of weight
lengthmaximal solution of .
.
Claim 2 Suppose that has solutions and is randomly chosen from
Then, $Pr$ [ $F(x,$ $w)$ is a maximal solution of ] $\geq 1-2^{-e(|x|)}$ .
, the functions
Proof. Since is randomly chosen from. Note that $n_{2}=$constructed in Step 3 must be random -weight functions over
. Thus, from Claim 1 and Lemma 3.1, we have that
$Pr$ [ $F(x,$ $w)$ is a maximal solution of]$1\leq k\leq e(|x|))a_{k,1}a_{k,2}\cdots a_{k,n_{1}}$ is a maximal solution of$=Pr$ []$\geq Pr[(\exists k, 1\leq k\leq e(|x|))x$ has a unique solution with maximum length and of
maximum weight under ]$\geq 1-\Pi_{k=1}^{e(|x|)}Pr[x$has two or more solutions with maximum length and of maximum
weight under ]$f_{k}$$m_{k}$$n_{1}$$T$$a_{k,1}a_{k,2}\cdots a_{k,n_{1}}$$x$$\{0,1\}^{p(|x|)}$

$w$

$x$

$x$

$\{0,1\}^{p(|x|)}$$w$$f_{1},$$f_{2},$$\cdots,$$f_{e(|x|)}$$[1, n_{x}]$$n_{2}$$2^{1+\beta og_{2}n_{*}\rceil}\geq 2n_{x}$

$x$

$x$

$(\exists k,$$f_{k}$$f_{k}$$\geq 1-(\frac{1}{2})^{e(|x|)}=1-2^{-e(|x|)}$1.

In the case when has no solution, $F(x, w)$ is undefined for all $w\in\{0,1\}^{p(|x|)}$ by Stepby Claim 2
1 and hence $G(x)=\emptyset$ . On the other hand, when has solutions,$G(x)$
is a maximal solution of by Claimand the definition of , and each element of
1. Therefore, solves .
If $G(x)=\emptyset$ , we know that has no solution by the discussions in the last paragraphand thus that $F(x, w)$ is undefined for all $w\in\{0,1\}^{p(|x|)}$ by Step 1. On the other hand,, then has solutions by the discussions in the last paragraph, $Pr[F(x, w)\in$
if$G(x)\cup\{\#\}]=1$ by Step 6 and the definition of, and $Pr[F(x, w)\in G(x)]\geq 1-2^{-e(|x|)}$.
by Claim 2. Therefore, is in\S$x$$G(x)\neq\emptyset$

$x$

$G$

$G$

$x$

$Q$

$x$

$G(x)\neq\emptyset$

$x$

$G$

$G$

4

$RP\cdot FP_{||}^{\Sigma_{2}^{P}}$Hardness of solving MAXP’s

In the light of Proposition 3.1(1), the following proposition shows that FP is a tightlower bound on the complexity of solving MAXP’s whose instance-solution relation is
P-decidable and hereditary.

Proposition 4.1 There is MAXP $Q=(D, R)$ such thatitary and is hard for FP.

$R$

is P-decidable and hered-$Q$

By Proposition 3.1(2), the following theorem shows that $NPMV\parallel OptP[O(\log n)]$ is atight lower bound on the complexity of solving MAXP’s whose instance-solution relationis P-decidable but not hereditary.

Theorem 4.1 There is a MAXP $Q=(D, R)$ such that
hereditary) and is hard for $NPMV\parallel OptP[O(\log n)]$ .

$R$

is P-decidable (but not$Q$

The following corollary is immediate from the proof of Theorem 4.1.
Corollary 4.1 The following problem (called $X$ -MaxModel hereafter) is complete for$NPMV\parallel OptP[O(\log n)]$ :Instance: A CNF boolean formula and a subset $X$ of the set of variables in .
Output: A truth assignment to the variables in $X$ such that can be extended toa satisfying truth assignment to but no withandcan be extended to$\phi$$\phi$$aarrow$$aarrow$$barrow$$\phi$$aarrow\subset barrow$$|\vec{a}|=|b|arrow$

18

a satisfying truth assignment to .
$\phi$-MaxModel is essentially the same problem as considered by Papadimitriou in Section 3 of [9]. In [9], Papadimitriou claimed without a precise proof that the problem iscomplete for $FP^{NP}$ . However, he later withdrew his claim and thus left the complexity ofthe problem open [10]. In [3], we proved that the complexity of the problem is roughly. Now, Corollary 4.1 gives, for the first time, the exact complexity ofcaptured by
the problem. Corollary 4.1 is also of special interest in the sense that no natural problem
complete for $NPMV\parallel OptP[O(\log n)]$ has been shown before.
By modifying the proof of Theorem 4.1, we can show that $NPMV\parallel OptP[O(\log n)]$ is atight lower bound on the complexity of solving MAXP’s whose instance-solution relation
is NP-decidable and hereditary.
$X$$FP_{||}^{NP}$

Theorem 4.2 There is a MAXP $Q=(D, R)$ such that
hereditary and is hard for $NPMV\parallel OptP[O(\log n)]$ .

$R$

is NP-decidable and$Q$

The instance-solution relation of $X$ -MaxModel is NP-decidable but not hereditary. A
natural question arises: Are there natural MAXP’ssuch thatis hard for $NPMV/$$/OptP[O(\log n)]$and the instance-solution relation ofis either NP-decidable andhereditary or P-decidable (but not hereditary)? Unfortunately, we are unable to settle
this question. However, we below show that the question will have a positive answer if$NPMV\parallel OptP[O(\log n)]$ in it is replaced by
.
$Q$

$Q$

$Q$

$FP_{||}^{NP}$Deflnition 4.1 A MAXP $Q=(D, R)$ is paddable if there are two functions and,in FP such that for every list $I=(x_{1},$of instances of $Q,$ $f(I)\in D$ and forevery maximal solution of $f(I),$ $g(I, w)$ gives a maximal solution for each .
$f$$x_{2},$$\cdots$$g$$x_{m}\rangle$$w$$x_{i}$

Lemma 4.1 If a MAXP is paddable and hard for NP, then it is hard for$FP_{||}^{NP}$.

Theorem 4.3 The following MAXP’s are hard for.
(1) MAXIMAL MODEL (MaxModel)
Instance: A CNF boolean formula .
Output: A maximal satisfying truth assignment to , i.e., a satisfying truth assignment
to such that there is no other satisfying truth assignment to with.
(2) MAXIMAL CUBIC SUBGRAPH (MaxCubSubgraph)
Instance: An undirected graph .
Output: A maximal subset $F$ of $E(G)$ such that every vertex in the graph $(V(G), F)$
has either degree 3 or degree . (Note: $V(G)$ and $E(G)$ denote hereafter the sets ofvertices and edges of , respectively.)(3) MAXIMAL SATISFIABILITY (MaxSat)
Instance: A CNF boolean formula $\phi=\{C_{1}, C_{2}, \cdots, C_{m}\}$ .
Output: A maximal subset of that is satisfiable.
(4) MAXIMAL k-COLORABILITY $(k\geq 3)$ (Max-k-Colorability)
Instance: An undirected graph .
Output: A maximal subset of $V(G)$ whose induced subgraph is k-colorable.
(5) MAXIMAL HAMILTONIAN SUBGRAPH (MaxHamSubgraph)
Instance: A pairof a connected undirected graph and a vertex in .
$FP_{||}^{NP}$$\phi$$\phi$$\vec{a}$$\vec{a}\subset barrow$$\sim b$$\phi$$\phi$

$G$

$0$

$G$

$\phi’$$\phi$$G$$\langle G, w\rangle$

$G$

19

$U$

Output: A maximal subset
has a Hamiltonian circuit.

$U$of $V(G)$ such that $w\in U$ and the subgraph induced by-hardness of MaxModel has been given
We here note that a different proof for thein [3]. Note that the instance-solution relations of the first two problems in Theorem 4.3
are P-decidable but not hereditary, while the instance-solution relations of the third andfourth problems in Theorem 4.3 are NP-decidable and hereditary. The last problem in
Theorem 4.3 is a concrete MAXP whose instance-solution relation is NP-decidable but
not hereditary.
For those MAXP’s whose instance-solution relation is coNP-decidable and hereditary, we are only able to show a loose lower bound.
$FP_{||}^{NP}$$Q$

Proposition 4.2 There is a MAXP $Q=(D, R)$ such that.
hereditary relation and is hard for
$Q$

$R$

is a coNP-decidable$FP_{||}^{NP}$is a nearly opIn the light of Theorem 3.1(2), the following theorem shows thattimal lower bound on the complexity of solving MAXP’s whose instance-solution relationis coNP-decidable but not hereditary.
$FP_{||}^{\Sigma_{2}^{P}}$Theorem 4.4 There is a MAXP $Q=(D, R)$ such thatis hard for.

$R$

is coNP-decidable and$Q$$FP_{||}^{\Sigma_{2}^{P}}$5

Characterizations of $coNP,$$D^{P}$

and$\Pi_{2}^{P}$

The following proposition can be easily proved.

Proposition 5.1 Let $Q=(D, R)$ be a MAXP.
is in P.
(1) If is P-decidable and hereditary, then(2) If is P-decidable, thenis in $coNP$ .
is in(3) If is NP-decidable, then.
is in(4) If is coNP-decidable and hereditary, thenis in.
(5) If is coNP-decidable, then$R$

$L_{Q}$$R$$L_{Q}$$R$$L_{Q}$$D^{P}$$R$$L_{Q}$$R$$L_{Q}$$D^{P}$.

$\Pi_{2}^{P}$

is a tight lower bound on
Similar to Proposition 4.1, we can simply show thatfor MAXP’s whose instance-solution relation is P-decidable andthe complexity ofhereditary.
, and
The following theorem gives us characterizations of $coNP,$
via MAXP’s.
$P$$L_{Q}$$Q$$D^{P}$$\Pi_{2}^{P}$

Theorem 5.1 The following hold:(1) A set is in $coNP$ if and only if it can be expressed as $L=\{x$ : $f(x)$ is a maximal
solution of in } for some $f\in FP$ and some MAXP whose instance-solution relationis P-decidable.
if and only if it can be expressed as $L=\{x$ : $f(x)$ is a maximal(2) A set is insolution of in } for some $f\in FP$ and some MAXP whose instance-solution relation
is NP-decidable (and hereditary).
(3) A set is in
if and only if it can be expressed as $L=\{x$ : $f(x)$ is a maximal
solution of in } for some $f\in FP$ and some MAXP whose instance-solution relationis coNP-decidable and hereditary.
$L$

$Q$

$x$

$D^{P}$

$L$

$Q$

$x$

$Q$

$D^{P}$

$L$

$x$

$Q$

$Q$

$Q$

20
if and only if it can be expressed as $L=\{x$ : $f(x)$ is a maximal(4) A set is insolution of in } for some $f\in FP$ and some MAXP whose instance-solution relationis coNP-decidable.
$L$

$x$

$\Pi_{2}^{P}$

$Q$

$Q$

Ekom the proof of Theorem 5.1(1), we easily see that there is a MAXP whose instancesolution relation is P-decidable (but not hereditary) and whose associated decision prob-complete for $coNP$ . However, the following proposition gives us two concrete
lem issuch MAXP’s.
$\leq_{m}^{P}$

Proposition 5.2 The decision problems associated with MaxModel and MaxCub-complete for $coNP$ :Subgraph are$\leq_{m}^{P}$

The following corollary follows immediately from the proof of Theorem 5.1(2) and
Cook’s theorem.

Corollary 5.1 The decision problem associated with $X$ -MaxModel isfor$D^{P}$.

$\leq_{m}^{P}$-complete

We next show three natural MAXP’s whose instance-solution relations are in NP and-complete for.
whose associated decision problems are$D^{P}$$\leq_{m}^{P}$

Proposition 5.3 The decision problems associated with MaxSat, Max-k-Colorability-complete for:and MaxHamSubgraph are$D^{P}$$\leq_{m}^{P}$

We next show a natural MAXP whose instance-solution relation is coNP-decidable-complete for. Otherand hereditary and whose associated decision problem issuch natural MAXP’s may be found in [2,11,12].
$D^{P}$$\leq_{m}^{P}$-complete for
Proposition 5.4 The following problem is:$X$, where is a CNF boolean formula,is a set of variables
Instance: A triple
appearing only positively in , and is a truth assignment to the variables in $X$ .
Question: Is it the case thatno extension satisfying but eachwithhas an extension satisfying ?
$D^{P}$$\leq_{m}^{P}$$\langle\phi, X, aarrow\rangle$$\phi$$\vec{a}$$\phi$$aarrow has$$\vec{a}\subsetarrow b$

6$\phi$$arrow b\in\Sigma^{||X||}$$\phi$

Conclusion

In this paper, we have suggested a general framework for studying the complexity ofsolving maximization problems. Our results are summarized in Table 1 and Table 2. The
results give, systematically, characterizations of several important complexity classes via
MAXP’s. An important consequence of the results is that the complexity of the problem
X-MinModel is exactly captured by NPMV\parallel OptP $[O(\log n)]$ , giving an answer to an
open question of Papadimitriou [9].
As seen from Table 1, the complexity of solving those MAXP’s whose instance-solution
relation is coNP-decidable and hereditary is unclear. Two obvious open questions are to
ask whether the trivial upper bound $FP^{NP}$ can be lowered and to ask whether the trivial
lower boundcan be raised. As a step toward the investigation of the two questions,
we may first consider what is the complexity of solving MinUnsat (or other natural such
$FP_{||}^{NP}$麗融総濫麟蕪\iota e 擁膿黙瓢農糖拙 nhge

$problMinU$

21-hardness of the decision problem associated with MinUnsat do not work [11]. Also,
showing that MinUnsat is solvable in a class below $FP^{NP}$ needs new ideas; at least, ourideas used in the proof of Theorem 3.1 do not seem to be applicable.
It would be also interesting to consider the complexity of MAXP’s whose instancebelow P.
solution relation is C-decidable and hereditary for some complexity class
These MAXP’s are obviously solvable in FP. Are they solvable in a class below FP or is
reductions)?
there such a MAXP that solving is complete for FP (say, under$C\subseteq
NC$ .
The two questions are important in parallel computation in the case when
$D^{P}$

$C$

$Q$

$Q$

$\leq_{1}^{NC_{T}}$References[1] R. Anderson, A Parallel Algorithm for the Maximal Path Problem, Proc. 17th A CM
Symposium on Theory of Computing (1985) 33-37.
[2] J.-Y. Cai and G.E. Meyer, Graph Minimal Uncolorability is
J. Comput., 16 (1987), pp. 259-277.

$D^{P}$-Complete, SIAM

[3] Z.-Z. Chen and S. Toda, The Complexity of Finding a Minimal Satisfying Truth
Assignment to a Boolean Formula, In submission (1992).
[4] Z.-Z. Chen, A Randomized NC Algorithm for the Maximal Tree Cover Problem,
Inform. Process. Lett. 40 (1991) 241-246.
[5] R.M. Karp and A. Wigderson, A Fast Parallel Algorithm for the Maximal Independent Set Problem, Proc. 16th ACM Symposium on Theory of Computing (1984)

266-272.

[6] M.W. Krentel, The Complexity of optimization Problems, J. Comput. System Sci.,
36 (1988), pp. 490-509.
[7] M. Luby, A Simple Parallel Algorithm for the Maximal Independent Set Problem,
Proc. 17th ACM Symposium on Theory of Computing (1985) 1-10.
[8] K. Mulmuley, U.V. Vazirani and V.V. Vazirani, Matching is as Easy as Matrix
Inversion, Proc. 19th A CM Symposium on Theory of Computing (1987), pp. 345-

354.

[9] C.H. Papadimitriou, On Selecting a Satisfying Truth Assignment, Proc. 32nd IEEE
Symposium on the Foundations of Computer Science (1991), pp. 163-169.

[10] C.H. Papadimitriou, Personal Communication (1992).

[11] C.H. Papadimitriou and D. Wolfe, The Complexity of Facets Resolved,, Proc. 26nd
IEEE Symposium on the Foundations of Computer Science (1985), pp. 74-78.
[12] C.H. Papadimitriou and M. Yannakakis, The Complexity of Facets (and Some Facetsof Complexity), J. Comput. System Sci., 28 (1982), pp. 244-259.