% The Chicago Journal of Theoretical Computer Science, Volume 1997, Article 1
% Published by MIT Press, Cambridge, Massachusetts USA
% Copyright 1997 by Massachusetts Institute of Technology
%
\newtoks\rstyle
\rstyle={cjlook}
%
\documentclass[v1.1,published]{cjstruct}
%
% Local style resources for this article.
%
\usestyleresource{amstex}
%
% Local macro definitions for this article.
%
\catcode`\@=11
\ifx\nopagebreakbeginpar\undeftex
  \newcommand{\nopagebreakbeginpar}{\@beginparpenalty10000}
\fi
\catcode`\@=12
%
\newcommand\nohyphenl[1]{{\discretionary{}{}{}{#1}}}
%
\newcommand{\orderle}[1]{O(#1)}
\newcommand{\ordereq}[1]{\Theta(#1)}
\newcommand{\orderlt}[1]{o(#1)}
\newcommand{\orderge}[1]{\Omega(#1)}
\newcommand{\circuitsize}[1]{\mathopen{|}#1\mathclose{|}}
\newcommand{\inputsize}[1]{\mathopen{|}#1\mathclose{|}}
\newcommand{\setsize}[1]{\mathopen{|}#1\mathclose{|}}
\newcommand{\polylog}{\operatorname{polylog}}
\newcommand{\polynomial}{\operatorname{poly}}
\mathstyleclass{\complexityclass}{\mathord}{\textsl}
\newcommand{\flanguage}[1]{\mathcal{#1}}
\newcommand{\setofset}[1]{\mathcal{#1}}
\newcommand{\program}[1]{\mathcal{#1}}
\newcommand{\setintsct}{\cap}
\newcommand{\mult}{\cdot}
\newcommand{\problemlabel}[1]{\textmd{\textsc{#1}}}
\newcommand{\prooffontshape}{\fontshape{n}\selectfont}
%
% Macros for the publisher's comment
%
% The circle R symbol for a registered trade name is adapted from the
% circled c copyright symbol defined in The TeXBook by Donald Knuth.
%
\def\registered{\({}^{\ooalign%
    {\hfil\raise.07ex\hbox{{\tiny\textup{R}}}%
    \hfil\crcr\scriptsize\mathhexbox20D\cr}}\)}
%
% end of local macro definitions for this article
%
\begin{document}
%
\begin{articleinfo}
%
\publisher{The MIT Press}
%
\publishercomment{%
  {\Large
    \begin{center}
      Volume 1997, Article 1\\
      \textit{12 March 1997}
    \end{center}
  }
  \par\noindent
  ISSN 1073--0486\@. MIT Press Journals, 55 Hayward St., Cambridge, MA
  02142 USA; (617)253-2889;
  \emph{journals-orders@mit.edu, journals-info@mit.edu}\@.
  Published one article at a time in \LaTeX\ source form on the
  Internet\@. Pagination varies from copy to copy\@. For more
  information and other articles see:
  \begin{itemize}
    \item \emph{http://www-mitpress.mit.edu/jrnls-catalog/chicago.html}
    \item \emph{http://www.cs.uchicago.edu/publications/cjtcs/}
    \item \emph{ftp://mitpress.mit.edu/pub/CJTCS}
    \item \emph{ftp://cs.uchicago.edu/pub/publications/cjtcs}
  \end{itemize}
  \sentence
  \par\noindent
  The \emph{Chicago Journal of Theoretical Computer Science} is
  abstracted or indexed in \emph{Research Alert,\registered
  SciSearch,\registered Current Contents\registered/Engineering
  Computing \& Technology}, and \emph{CompuMath Citation Index\@.\registered}
}
%
\copyrightstmt{%
  \copyright 1997 The Massachusetts Institute of Technology\@.
  Subscribers are licensed to use journal articles in a variety of
  ways, limited only as required to insure fair attribution to authors
  and the journal, and to prohibit use in a competing commercial
  product\@. See the journal's World Wide Web site for further
  details\@. Address inquiries to the Subsidiary Rights Manager, MIT
  Press Journals; (617)253-2864;
  \emph{journals-rights@mit.edu}\@.\pagebreak[2]
}
%
\journal{Chicago\nolinebreak[1] Journal of Theoretical Computer\nolinebreak[1] Science}
\journalcomment{%
  The \emph{Chicago Journal of Theoretical Computer Science}
  is a peer-reviewed scholarly journal in theoretical computer
  science\@. The journal is committed to providing a forum for
  significant results on theoretical aspects of all topics in computer
  science\@.
  \par
  \begin{trivlist}
    \item[\emph{Editor in chief:}] Janos Simon
    \item[\emph{Consulting editors:}]
      Joseph Halpern, Stuart A.\ Kurtz, Raimund Seidel
    \item[\emph{Editors:}]
      \begin{tabular}[t]{lll}
        Martin Abadi & Greg Frederickson & John Mitchell \\
        Pankaj Agarwal & Andrew Goldberg & Ketan Mulmuley \\
        Eric Allender & Georg Gottlob & Gil Neiger \\
        Tetsuo Asano & Vassos Hadzilacos & David Peleg \\
        Laszl\'o Babai & Juris Hartmanis & Andrew Pitts \\
        Eric Bach & Maurice Herlihy & James Royer \\
        Stephen Brookes & Ted Herman & Alan Selman \\
        Jin-Yi Cai & Stephen Homer & Nir Shavit \\
        Anne Condon & Neil Immerman & Eva Tardos \\
        Cynthia Dwork & Howard Karloff & Sam Toueg \\ 
        David Eppstein & Philip Klein & Moshe Vardi \\
        Ronald Fagin & Phokion Kolaitis & Jennifer Welch \\
        Lance Fortnow & Stephen Mahaney & Pierre Wolper \\
        Steven Fortune & Michael Merritt
      \end{tabular}
    \vspace{1ex}
    \item[\emph{Managing editor:}] Michael J.\ O'Donnell
    \vspace{1ex}
    \item[\emph{Electronic mail:}] \emph{chicago-journal@cs.uchicago.edu}
  \end{trivlist}
\sentence
\pagebreak[0]
}
%
\bannerfile{cjtcs-banner.tex}
%
\volume{1997}
%
\articleid{1}
%
\selfcitation{
     @article{cj97-01,
       author={Uriel Feige and Joe Kilian},
       title={On Limited versus Polynomial Nondeterminism}
       journal={Chicago Journal of Theoretical Computer Science},
       volume={1997},
       number={1},
       publisher={MIT Press},
       month={March},
       year={1997}
     }
}
%
\begin{retrievalinfo}
\end{retrievalinfo}
%
\title{On Limited versus Polynomial Nondeterminism}
\shorttitle{Limited vs.\ Polynomial Nondeterminism}
%
\begin{authorinfo}
%
% Correction to error in cjstruct.sty version 1.1.
%
\def\fixversion{1.1}
\ifx\cjversion\fixversion
  \renewcommand{\printname}[1]{
    \global\authorstring={#1}
    \global\authorstrue
    \ifinfo\item Printed name: #1\fi
  }
\fi
%
% End of correction.
%
   \printname{Uriel Feige}
   \collname{}{Feige, Uriel}
   \begin{institutioninfo}
       \instname{Weizmann Institute}
       \department{Department of Applied Math and Computer Science}
       \address{}{Rehovot}{}{Israel}{76100}
   \end{institutioninfo}
   \email{feige@wisdom.weizmann.ac.il}
\end{authorinfo}
%
\begin{authorinfo}
   \printname{Joe Kilian}
   \collname{}{Kilian, Joe}
   \begin{institutioninfo}
       \instname{NEC Research Institute}
       \department{}
       \address{4 Independence Way}{Princeton}{NJ}{USA}{08540}
   \end{institutioninfo}
   \email{joe@research.nj.nec.com}
\end{authorinfo}
%
\shortauthors{Feige and Kilian}
%
\support{Some of the research in this article was accomplished while
  Uriel Feige was visiting the NEC Research Institute\@.}
%
\begin{editinfo}
  \submitted{21}{11}{1995}\reported{31}{5}{1996}
  \submitted{24}{7}{1996}\reported{20}{11}{1996}
  \submitted{7}{1}{1997}\published{12}{3}{1997}
\end{editinfo}
%
\end{articleinfo}
%
\begin{articletext}
%
\begin{abstract}
%
\apar{Abstract-1}
In this paper, we show that efficient algorithms for some problems
that require limited nondeterminism imply the subexponential
simulation of nondeterministic computation by deterministic
computation\@. In particular, if cliques of size \(\orderle{\log n}\)
can be found in polynomial time, then nondeterministic time \(f(n)\)
is contained in deterministic time \(2^{\orderle{\sqrt{f(n)\polylog f(n)}}}\)\@.
%
\end{abstract}
%
\asection{1}{Introduction}
%
\apar{1-1}
A major open question in computational complexity is whether
\(\complexityclass{P}=\complexityclass{NP}\)\@. In other words, is it
true that if a language \(\flanguage{L}\) can be recognized in time
\(f(n)\) by a nondeterministic Turing machine (where \(n\) denotes the
input length), then \(\flanguage{L}\) can be recognized in time
\((f(n))^{c}\) by a deterministic Turing machine (for some constant
\(c\))\@? Let \(\complexityclass{DTIME}(f(n))\) denote the class of
languages accepted by a deterministic Turing machine in time
\(\orderle{f(n)}\), and let \(\complexityclass{NTIME}(f(n))\) denote
the class of languages accepted by a nondeterministic Turing machine
in time \(\orderle{f(n)}\)\@. The trivial relations between these
classes are
\(\complexityclass{DTIME}(f(n))\subset\complexityclass{NTIME}(f(n))\)
(by definition), and
\(\complexityclass{NTIME}(f(n))\subset\complexityclass{DTIME}(2^{O(f(n))})\)
(by exhaustive search)\@. Perhaps the only nontrivial relation known
is that
\(\complexityclass{DTIME}(n)\neq\complexityclass{NTIME}(n)\)
\cite{cj97-01-17}\@.
%
\apar{1-2}
A natural question to ask is whether there is a general methodology
that improves over exhaustive search, and applies to a wide range of
\(\complexityclass{NP}\) problems\@. For some specific
\(\complexityclass{NP}\) problems, improvements over exhaustive search
that involve the constant in the exponent were
obtained~\cite{cj97-01-24,cj97-01-23,cj97-01-04}\@. However, we seek
a more dramatic improvement, with more general applicability\@. This
leads to the following question:
%
\begin{alabsubtext}{Question}{1}{}
%
Is there a subexponential deterministic simulation of
nondeterministic computation\@? More explicitly, is there some
constant \(\delta<1\) such that
\(\complexityclass{NTIME}(f(n))\subset
\complexityclass{DTIME}(2^{\orderle{f(n)^{\delta}}})\)\@?
%
\end{alabsubtext}
\sentence
%
\apar{1-3}
Certain \(\complexityclass{NP}\) problems require only a limited
amount of nondeterminism, in the sense that their (natural)
\(\complexityclass{NP}\)-witness is at most polylogarithmic in the
input length\@. For such problems, improvements over exhaustive
search are sometimes dramatic\@. Examples of problems that require
limited nondeterminism can be constructed by considering parameterized
versions of \(\complexityclass{NP}\) optimization problems, in which
the parameter \(k\) is restricted to be small (typically constant, or
\(\orderle{\log n}\))\@. In the problem definitions below, \(k\) is a
positive-integer input parameter\@.
%
\paragraph{Path}
%
\begin{description}
%
\item[\problemlabel{Instance:}] A graph \(G\) of order \(n\)\@.
%
\item[\problemlabel{Question:}] Does \(G\) contain a simple path of length 
at least \(k\)\@?
%
\end{description}
%
\paragraph{Vertex Cover}
%
\begin{description}
%
\item[\problemlabel{Instance:}] A graph \(G\) of order \(n\)\@.
%
\item[\problemlabel{Question:}] Does \(G\) contain a set of vertices of 
cardinality at most \(k\) that is incident with every edge of \(G\)\@?
%
\end{description}
%
\paragraph{Clique}
%
\begin{description}
%
\item[\problemlabel{Instance:}] A graph \(G\) of order \(n\)\@.
%
\item[\problemlabel{Question:}] Does \(G\) contain a complete subgraph of
order at least \(k\)\@?
%
\end{description}
%
\paragraph{Monotone Circuit Satisfiability}
%
\begin{description}
%
\item[\problemlabel{Instance:}] A monotone circuit \(C\) on \(n\)
Boolean inputs\@.
%
\item[\problemlabel{Question:}] Does \(C\) accept an input vector of Hamming
weight at most \(k\)\@?
%
\end{description}
%
\paragraph{Tournament Dominating Set}
%
\begin{description}
%
\item[\problemlabel{Instance:}] A digraph \(G=(V,E)\) of order \(n\),
in which for every pair of vertices \(u,v\in V\), 
either \((u,v)\in E\) or \((v,u)\in E\)\@.
%
\item[\problemlabel{Question:}] Find a set \(D\subset V\) of minimum
cardinality such that for each vertex \(v\in V\), there is an edge
\((u,v)\in E\) for some vertex \(u\in D\)\@.
%
\end{description}
%
\paragraph{VC Dimension}
%
\begin{description}
%
\item[\problemlabel{Instance:}] A set \(U\) of cardinality \(n\) and
a family \(\setofset{F}\) of \(n\) subsets of \(U\)\@.
%
\item[\problemlabel{Question:}] Find a set \(S\subset U\)
of maximum cardinality that is \emph{shattered} by \(\setofset{F}\)\@.
Set \(S\) is shattered by \(\setofset{F}\) if for every subset
\(T\subset\setofset{F}\) there is a set \(A\in\setofset{F}\) such that
\(A\setintsct S=T\)\@.
%
\end{description}
%
We remark that the last two problems above are search problems, rather
than decision problems, and also that there is no explicit parameter
\(k\) involved\@. However, a parameter of \(k\simeq\log n\) is
implicit, since the cardinality of the optimal solution is at most
\(\log n+1\)\@.
%
\apar{1-4}
For the problems above, with parameter \(k=\log n\), an exhaustive
search requires time of roughly \(n^{\log n}\)\@. However, the first
two of these problems have algorithms of time complexity
\(\orderle{n^{c}2^{k}}\), for some constant \(c\), which is polynomial
even for \(k=\log n\)~\cite{cj97-01-20,cj97-01-09,cj97-01-03}\@. (Note
that these two problems are \(\complexityclass{NP}\)-hard for a
general \(k\), since the Vertex Cover and
Hamiltonian Path problems are\@.) Is this phenomenon of
dramatically improving over exhaustive search a general one when
problems that require a limited amount of nondeterminism are
concerned\@? Does the same apply for the \(k\)-Clique problem when
\(k=\orderle{\log n}\)\@? These types of questions are treated by the
theory of \emph{fixed parameter intractability}~\cite{cj97-01-08}, and
motivate the introduction of the complexity class
\(\complexityclass{LOGSNP}\)~\cite{cj97-01-20}\@. We shall return to
discuss these notions in Section~4.2.1\@. For now, we shall
concentrate on the \(\log\)-Clique problem in which one must
find a clique of size \(k\simeq\log n\) in the input graph\@.
%
\begin{alabsubtext}{Question}{2}{}
%
Is the \(\log\)-Clique problem solvable in polynomial time\@?
%
\end{alabsubtext}
%
\apar{1-5}
Our main result is a connection between Question~2, that deals with a
case of limited nondeterminism, and Question~1, that deals with
polynomial nondeterminism\@. In Section~2 we show that if the answer
to Question~2 is positive, then so is the answer to Question~1\@. In
Section~3 we present extensions that deal with the complexity of
finding approximate solutions to the \(k\)-Clique problem, for small
values of \(k\)\@. In Section~4 we discuss our results and their
implications\@. In particular, we discuss related work showing (for
the \(k\)-Monotone Circuit Satisfiability problem~\cite{cj97-01-01})
or implying in conjunction with our work (for the Tournament
Dominating Set and VC-Dimension problems~\cite{cj97-01-20})
additional problems of limited nondeterminism whose complexity is
related with subexponential simulation of \(\complexityclass{NP}\)\@.
%
\asection{2}{On the Complexity of the
{\mathversion{bold}\protect\(\log\protect\)}-Clique \nohyphenl{Problem}}
%
\apar{2-1}
The results of this section were first proven as corollaries of the
results of Section~3\@. The elementary proofs given here were noticed
by Noam Nisan, who permitted us to use them\@.
%
\apar{2-2}
\begin{alabsubtext}{Lemma}{1}{}
%
Suppose there is a polynomial time algorithm for the \(k\)-Clique problem
when \(k\le\log n\)\@. Then the \(k\)-Clique problem is solvable in time
\(\orderle{n^{\orderle{\sqrt{n}}}}\), for every \(k\)\@. 
%
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Lemma}{1}{}
\prooffontshape
%
\apar{Prove Lemma 1-1}
Let \(\program{A}\) be an algorithm that in time \(\orderle{n^c}\)
solves the \(k\)-Clique problem for \(k\le\log n\)\@. Let \((G,k)\)
be an input instance for the \(k\)-Clique problem (with arbitrarily
large \(k\))\@. Reduce \((G,k)\) to a new instance
\((\hat{G},\hat{k})\) of the \(k\)-Clique problem as follows\@.
Without loss of generality, assume that \(k\) is a perfect square\@.
(Otherwise, let \(k'\) be the least perfect square greater than
\(k\)\@. Add \(k'-k\) vertices to \(G\), connected to every other
vertex\@.) Graph \(\hat{G}\) contains \(N={n\choose\sqrt{k}}\)
vertices, where each vertex of \(\hat{G}\) corresponds to a
\(\sqrt{k}\)-subset of vertices of \(G\)\@. Two vertices of
\(\hat{G}\) are connected by an edge if the \(2\sqrt{k}\) vertices
that they correspond to are distinct and form a clique of size
\(2\sqrt{k}\) in \(G\)\@. Set \(\hat{k}=\sqrt{k}\)\@.
%
\begin{alabsubtext}{Proposition}{1}{}
%
\(\hat{G}\) has a \(\hat{k}\)-clique if and only if \(G\) has a \(k\)-clique\@.
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Proposition}{1}{}
\prooffontshape
%
\apar{Prove Prop 1-1}
If \(G\) has a \(k\)-clique, then partition the vertices of this clique
into \(\sqrt{k}\) sets of size \(\sqrt{k}\)\@. These sets make up
\(\sqrt{k}=\hat{k}\) vertices of \(\hat{G}\) that together form a clique
in \(\hat{G}\)\@.
%
\apar{Prove Prop 1-2}
If \(\hat{G}\) has a \(\hat{k}\)-clique, then the vertices of \(G\)
comprising each vertex of this \(\hat{k}\)-clique are all distinct,
and form a clique of size \(\sqrt{k}\mult\sqrt{k}=k\) in \(G\)\@.
%
{\nopagebreakbeginpar\markendlst{Proof of Proposition 1}}
\end{alabsubtext}
%
\apar{Prove Lemma 1-2}
The number of vertices of \(\hat{G}\) is
\(N={n\choose\sqrt{k}}<n^{\sqrt{n}}\)\@. The construction of the edges
of \(\hat{G}\) takes time \(\orderle{N^{2}}\), times some polynomial
in \(n\) reflecting the time it takes to check whether \(2\sqrt{k}\)
vertices form a clique in \(G\)\@. Hence the reduction from \((G,k)\)
to \((\hat{G},\hat{k})\) takes time \(n^{\orderle{\sqrt{n}}}\)\@. The
value of \(\hat{k}\) satisfies \(\hat{k}\le\log N\)\@. Therefore, the
\(k\)-Clique problem on \((\hat{G},\hat{k})\) can be solved in
time \(\orderle{n^{c\sqrt{n}}}\), using algorithm \(\program{A}\)\@.
The proof of the lemma follows from Proposition~1\@.
%
{\nopagebreakbeginpar\markendlst{Proof of Lemma 1}}
\end{alabsubtext}
%
\apar{2-3}
Lemma~1 shows that if the \(\log\)-Clique problem is in
\(\complexityclass{P}\), then a specific \(\complexityclass{NP}\)
problem has subexponential complexity\@. The conclusion can be
extended to some other \(\complexityclass{NP}\) problems---those from
which there is a linear (or slightly superlinear) reduction to
the \(k\)-Clique problem\@.  In particular, let \(\flanguage{L}\) be
a language in \(\complexityclass{NTIME}((f(n))\), where \(f(n)\) is a
proper complexity function (as defined in~\cite{cj97-01-15}, for
example)\@. Then the reductions of Pippenger and
Fischer~\cite{cj97-01-16} show that it has a uniform family of
nondeterministic circuits \(C_{L}(n)\) of bounded fan-in and size
\(f'(n)=\orderle{f(n)\log f(n)}\)\@. To check whether
\(x\in\flanguage{L}\), one determines whether input \(x\) is accepted
by the nondeterministic circuit \(C_{L}(n)\), where \(n\) is the
length of \(x\)\@. This problem can be reduced to
the \(k\)-Clique problem on a graph with \(\orderle{f'(n)}\)
vertices\@. Hence we obtain the following\@.
%
\begin{alabsubtext}{Theorem}{1}{}
%
Suppose there is a polynomial time algorithm for the
\(\log\)-Clique problem\@. Then there is a deterministic
subexponential simulation of nondeterministic computations\@.
Specifically, for each proper complexity function \({f(n)>n}\),
\(\complexityclass{NTIME}(f(n))\) is contained in
\(\complexityclass{DTIME}((f'(n))^{\sqrt{f'(n)}})\), where
\(f'(n)=\orderle{f(n}\log f(n))\)\@.
%
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Theorem}{1}{}
\prooffontshape
%
\apar{Prove Theorem 1-1}
The theorem follows trivially from the discussion preceding it\@.
For thoroughness, we explain the reduction from the Nondeterministic
Circuit Value problem to Clique\@. Recall that a family of circuits
for language \(\flanguage{L}\) has a different circuit \(C_{L}(n)\)
for each input size \(n\)\@. The circuit has \emph{and}, \emph{or},
and \emph{not} gates of fan-in \(2\) (or \(1\), for \emph{not} gates)
and unbounded fan-out, \(n\) input wires that encode the input \(x\),
and one output wire\@. A circuit is nondeterministic if, in addition,
there are nondeterministic input wires (that encode the witness
\(w\))\@. If \(x\in\flanguage{L}\), there is a setting to these wires
so that the output is \(1\), and if \(x\notin\flanguage{L}\), then for
every setting to these wires, the output is \(0\)\@. The size of
circuit \(C\), denoted by \(\circuitsize{C}\), is the number of gates
in the circuit\@. The nondeterministic time for language
\(\flanguage{L}\) is a function of the input size \(n\), and is
defined as \(NT_{L}(n)=\min_{C_{n}}[\circuitsize{C_{n}}]\) (where
\(C_{n}\) correctly recognizes
\(\flanguage{L}\setintsct\{0,1\}^n\))\@. This is the usual
correspondence between circuit size and time\@. If we require that
the circuit family is efficiently constructible, then the
time-complexity measure that we consider is a \emph{uniform}
measure\@.
%
\apar{Prove Theorem 1-2}
To check whether a given nondeterministic circuit \(C\) of size \(m\)
accepts input \(x\), we may use the following reduction to
the \(k\)-Clique problem\@. Construct a graph \(G\) on at most
\(4m\) vertices that has a clique of size \(k=m\) if and only if the
circuit is accepting\@. Each input to a gate is labeled with a fresh
variable\@. A two-input gate can be represented by four vertices, one
for each combination of values to the two variables that are the input
of the gate\@. (If one of the variables is an input variable, then
include only vertices that are consistent with its value\@.) Each
vertex also implies a value for its respective output\@. For the
output gate of the circuit, include only the vertices that imply an
output of~\(1\) (\emph{accept})\@. Every pair of vertices in the
graph is connected by an edge, unless the vertices are contradictory
(they imply two different values for some variable)\@. The graph has a
clique of size \(m\) precisely when there is an assignment to the
nondeterministic inputs of the circuit that forces an output
of~\(1\)\@.
%
{\nopagebreakbeginpar\markendlst{Proof of Theorem 1}}
\end{alabsubtext}
%
\apar{2-4}
To put Lemma~1 and Theorem~1 in perspective, observe what would happen
if we had a polynomial time algorithm that finds cliques of size
\((\log n)^{2}\) in graphs\@. Then clearly, the \(k\)-Clique problem
would have a subexponential algorithm for every value of \(k\), simply
by padding the input graph by \(2^{\sqrt{k}}\) isolated vertices\@. A
similar observation applies to parameterized versions of many other
\(\complexityclass{NP}\) problems (such as the Path and
the Vertex Cover problems)\@. Hence the new element in our
connection between limited and polynomial nondeterminism is a
quantitative one, the level of limited nondeterminism in which such a
connection can be demonstrated\@.
%
\asection{3}{On Finding Small Cliques}
%
\apar{3-1}
As we have seen in Section~2, a polynomial time algorithm for finding
cliques of size \(k=\log n\) implies subexponential algorithms for
\(\complexityclass{NP}\) problems\@. In this section, we investigate
weaker conditions that imply subexponential algorithms for
\(\complexityclass{NP}\)\@. The condition \(k=\log n\) can be relaxed
to \(k=(\log n)^{\alpha}\), for every \(\alpha>0\)\@. Moreover, the
running time of the algorithm that finds small cliques can be slightly
superpolynomial, to an extent that depends on \(\alpha\)\@. We can
further relax our conditions if we are satisfied with a weaker
implication, that of the existence of \emph{randomized} subexponential
algorithms for \(\complexityclass{NP}\) problems\@. We present the
relaxed implication in Section~3.1, the relaxed conditions in
Section~3.2, and the reduction between the two in Section~3.3\@. This
reduction is more sophisticated than that of Section~2, and it uses
recent results from the theory of interactive proofs\@.
%
\asubsection{3.1}{The Goal: Subexponential Algorithms for
\protect\(\complexityclass{NP}\protect\)}
%
\apar{3.1-1}
It is most convenient to present our goal in the circuit model\@.
Recall that (nonuniform) computation time is associated with circuit
size, and let \(T_{L}(n)\) (\(NT_{L}(n)\)) denote the
(non)deterministic circuit complexity of language \(L\)\@. Clearly,
\(T_{L}(n)\leq 2^{\orderle{NT_{L}(n)}}\), since every function has
exponential-size circuits\@. Interpreting Question~1 in the
nonuniform circuit model, we obtain our first goal\@.
%
\begin{alabsubtext}{Goal}{1}{}
%
For some \(\epsilon>0\) and for every language \(L\), if time
complexity is measured as size of nonuniform circuit families, then
\[T_{L}(n)=\orderle{2^{(NT_{L}(n))^{1-\epsilon}}}\]
\sentence
%
\end{alabsubtext}
%
\apar{3.1-2}
There is also a uniform version of our goal\@. However, it involves
randomized algorithms\@. Since we will be dealing with
superpolynomial randomized algorithms, we allow ourselves a relaxed
notion of uniformity for nondeterministic circuits\@. It has the
additional advantage of considering the complexity of individual
instances, rather than clustering all size-\(n\) instances together\@.
%
\begin{alabsubtext}{Definition}{1}{}
%
A uniform randomized algorithm \(A\) is a \emph{weakly efficient
generator of nondeterministic circuits for language \(L\)} if it
has the following properties:
%
\begin{enumerate}
%
\item On input \(x\), \(A(x)\) outputs a 
nondeterministic circuit of size at most \(S_{A,x}\), drawn at random from
a distribution \(C_{A,x}\) of nondeterministic circuits\@.
%
\item \(A(x)\) runs in time subexponential in \(S_{A,x}\), that is in time
\(\orderle{2^{(S_{A,x})^{1-\epsilon}}}\)\@.
%
\item With probability at least \(2/3\) (over the coin tosses of \(A\)), 
the output circuit correctly decides (nondeterministically) whether
\(x\in L\)\@.
%
\end{enumerate}
\sentence
%
The weak uniform nondeterministic complexity of \(x\) relative to
\(A\) is \(S_{A,x}\)\@. 
%
\end{alabsubtext}
%
\apar{3.1-3}
The traditional notion of uniform circuit complexity is a special case
of Definition~1, when \(A\) runs in deterministic polynomial time with
unary input \(n=\inputsize{x}\)\@. Then \(A\) generates a uniform
nondeterministic circuit family for \(L\) with complexity
\(S_{A,1^{n}}\)\@.
%
\begin{alabsubtext}{Goal}{2}{}
%
For some \(\epsilon>0\) and for every language \(L\) that has a
corresponding generator of nondeterministic circuits \(A\), there
exists a uniform randomized algorithm \(B\) that decides \(L\), and
on input \(x\) runs in time
\[RT(x)=\orderle{2^{(S_{A,x})^{1-\epsilon}}}\]
\sentence
%
\end{alabsubtext}
%
\apar{3.1-4}
In Section~4.1, we further discuss Goals~1 and~2\@.
%
\asubsection{3.2}{The Challenge: Finding Small Cliques}
%
\apar{3.2-1}
We present our challenge, which is an algorithmic problem that, if
solved, would lead to our goals\@.
%
\begin{alabsubtext}{Challenge}{1}{}
%
Design a deterministic algorithm that for \(n\)-vertex graphs finds
a clique of size \(k\) in time \(\orderle{n^{k^{1-\epsilon}}}\) (if
indeed the graph has such a clique), where \(\epsilon>0\), and
\(k=\ordereq{(\log n)^{c}}\) for some \(c>0\)\@.
%
\end{alabsubtext}
%
\apar{3.2-2}
Observe that using exhaustive search, \(\orderle{n^{k}}\) time is
achievable\@. Observe also that we are not asking for a polynomial
time algorithm for finding small cliques, but just for a substantial
improvement over exhaustive search\@.
%
\apar{3.2-3}
Our challenge can be relaxed, while still serving its purpose:
%
\begin{alabsubtext}{Challenge}{2}{}
%
Design a randomized algorithm that distinguishes (with probability
at least 2/3) between graphs with maximum cliques of size at most
\(k\) and graphs with maximum cliques of size at least \(2k\)\@.
The running time of the algorithm is required to be
\(\orderle{n^{k^{1-\epsilon}}}\), where
\(k=\ordereq{(\log n)^{c}}\), for some \(c>0\), \(\epsilon>0\)\@. The
algorithm is not required to output a clique, just a decision\@.
%
\end{alabsubtext}
\sentence
%
\apar{3.2-4}
In Section~4.2, we discuss the plausibility of our challenges\@.
%
\asubsection{3.3}{The Reduction}
%
\apar{3.3-1}
Playing with the parameters of Lemma~1, one can verify that
Challenge~1, if met, implies a positive answer to Question~1\@. In
this section, we describe the reduction from Goals~1 and~2 to
Challenge~2\@. It is based on interactive proofs, and in particular
on proof systems developed by Polishchuk and
Spielman~\cite{cj97-01-18}\@. They show that the verification of
whether an input \(x\) of length \(n\) is accepted by a
nondeterministic circuit \(C\) of size \(m>n\) can be reduced to the
verification of a corresponding \emph{holographic proof} with the
following properties\@.
%
\begin{enumerate}
%
\item The holographic proof is just a string of bits\@. 
It is an \(\complexityclass{NP}\)-witness to the fact that \(x\) is
accepted bycircuit \(C\), which can be verified with high confidence
by examining at random only a few bits of the witness\@.
%
\item There is a uniform random polynomial-time verification
algorithm \(V\) associated with the holographic proof\@.
The number of random bits used by algorithm \(V\) is \(r\), where \(r\)
is bounded by some polynomial in \(m\)\@. 
%
\item Algorithm \(V\) queries 
the holographic proof at
\(q=\orderle{m^{\orderlt{1}}}\) bit locations\@. These locations are
selected at random, based on the \(r\) random bits\@.
%
\item If \(x\) is accepted by circuit \(C\), then there exists a
holographic proof \(h\) of length \(l=\orderle{m^{1+\orderlt{1}}}\)
that always causes \(V(x,C,h)\) to accept (regardless of the value of
the random bits used by \(V\))\@.
%
\item If \(x\) is not accepted by circuit \(C\), then for every string
\(h'\) of length \(l\), the probability that \(V(x,C,h')\) accepts
is at most \(1/2\) (known as the \emph{error probability})\@.
%
\end{enumerate}
%
\apar{3.3-2}
No familiarity with the concept of holographic proofs except for the
properties listed above is required of the reader\@. We remark that
the bounds that we require on \(l\) (the size of the holographic
proof), on \(q\) (the number of bits queried), and on \(r\) (the
number of random bits used), are weaker than those actually achieved
by Polischchuk and Spielman~\cite{cj97-01-18}\@.
%
\begin{alabsubtext}{Theorem}{2}{}
%
Challenge~2 implies Goals~1 and~2\@.
%
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Theorem}{2}{}
\prooffontshape
%
\apar{Prove Theorem 2-1}
We reduce the existence of the holographic proof described above to
the \(k\)-Clique problem\@. The reduction is based on
the reduction described by Feige et al.~\cite{cj97-01-11}, and on
subsequent extensions of Zuckerman~\cite{cj97-01-25}\@. We optimize
the parameters of the reduction to best serve our goal\@.
%
\apar{Prove Theorem 2-2}
The reduction proceeds in two phases\@. The goal of the first phase is
to reduce the number of random bits needed by the verifier to check
the holographic proof\@. In Polishchuk and
Spielman's~\cite{cj97-01-18} proof system, the verifier uses \(r\)
random bits, where \(r\ge\log m\)\@. For our construction, we need to
reduce the number of random bits used by the verifier while
maintaining a low error probability\@. We do this by considering two
different types of random bits that the verifier can use\@. One type
is \emph{private} random bits that the verifier gets after the prover
writes down the proposed holographic proof, as is the case in ordinary
holographic proofs\@. The other type is a table \(T\) of
\emph{public} random bits, to which the prover also has access before
writing down the proposed holographic proof\@. It turns out that for
our purpose, we only need to reduce the number of private random
bits\@. This reduction is made possible by the introduction of the
public random bits, and by an increase in the number of queried
bits\@.
%
\begin{alabsubtext}{Lemma}{2}{}
%
Assume that there is a holographic proof system with verifier \(V\)
for checking whether circuit \(C\) accepts input \(x\), with
parameters \(r\) (number of private random bits used by the
verifier), \(l\) (proof length), and \(q\) (number of query bits),
as described above\@. Let \(s>6\) be a parameter to be chosen
later\@. Then there is a holographic proof system with public table
\(T\) and verifier \(V'\) with the following properties\@.
%
\begin{enumerate}
%
\item The proof length is \(l\), the number of private random bits is
\(\log (3l/s)\), the number of queried bits is \(qs\), and the table
\(T\) contains \(3lr\) public random bits\@.
%
\item If \(x\) is accepted by circuit \(C\), then there exists a
holographic proof \(h\) of length \(l\) that always causes
\(V'(x,C,h,T)\) to accept (regardless of the value of the public and
private random bits)\@.
%
\item If \(x\) is not accepted by circuit \(C\), then most possible
tables \(T\) are \emph{typical}, where \(T\) is typical if for every
string \(h'\) of length \(l\), the probability (over the private
randomness) that \(V(x,C,h',T)\) accepts is at most \(1/2\)\@.
%
\end{enumerate}
%
\end{alabsubtext}
%
\begin{alabsubtext}{Proof of Lemma}{2}{}
\prooffontshape
%
\apar{Prove Lemma 2-1}
We describe the holographic proof system with public table \(T\) and
verifier \(V'\)\@. When \(x\) is accepted by circuit \(C\), the same
holographic proof \(h\) as in Polishchuk and Spielman's proof
system~\cite{cj97-01-18} serves as a holographic proof in our new
proof system, regardless of the contents of the table \(T\)\@.
Verifier \(V'\) proceeds as follows\@. Partition the table \(T\) of
size \(3lr\) into \(k=3l/s\) rows, where each row contains \(s\)
strings of length \(r\)\@. Let \(t_{ij}\) denote the \(j\)th string
of row \(i\) in table \(T\)\@. Using \(\log k\) private random bits,
\(V'\) selects a row \(i\) at random, and simulates the verifier \(V\)
of~\cite{cj97-01-18} \(s\) times, each time using a fresh string
\(t_{ij}\) (for \(1\le j\le s\)) as private random bits for \(V\)\@.
If \(V\) accepts in all \(s\) simulations, then \(V'\) accepts as
well\@. Otherwise, \(V'\) rejects\@.
%
\apar{Prove Lemma 2-2}
Properties~1 and~2 of Lemma~2 clearly hold\@. It remains to consider
the case where \(x\) is not accepted by circuit \(C\) and show that
most \(T\) are typical\@. In this case, fix a (false) holographic
proof \(h'\)\@. The probability that it is not exposed by \(s\)
simulations of \(V\), each time with random and independent private
coins, is at most \(2^{-s}\)\@. Hence the probability (over the
choice of \(T\)) that \(h'\) is not exposed by at least half of the
\(k\) random strings in the table \(T\) is at most
\(2^{k}2^{-ks/2}=2^{3l/s-3l/2}\ll 2^{-l}\) (for \(s>6\))\@. Since there are
only \(2^{l}\) possible false holographic proofs, it follows that with
high probability every such holographic proof is exposed by at least
\(k/2\) of the random strings in \(T\)\@. Hence for most choices of
\(T\), \(V'\) accepts with probability at most \(1/2\)\@.
%
{\nopagebreakbeginpar\markendlst{Proof of Lemma 2}}
\end{alabsubtext}
%
\apar{Prove Theorem 2-3}
The first phase of our reduction corresponds to the selection of a
table \(T\) with \(k=3l/s\) rows of \(rs\) random bits\@. The second
phase of our reduction is similar to the reduction of Feige et
al.~\cite{cj97-01-11}\@. We construct a \(k\)-partite graph
\(G\)\@. Each part of the graph corresponds to one of the \(k\) rows
of \(T\)\@. The vertices in each part are all strings of length
\(qs\), which represent all possible answer sequences to the \(qs\)
queried bits\@. A vertex is removed if the corresponding answer
sequence leads \(V'\) to reject\@. Two vertices (in different parts
of \(G\)) are connected by an edge if there exists some (possibly
false) holographic proof that is consistent with both vertices\@.
Graph \(G\) contains at most \(k2^{qs}\) vertices, and can be
costructed in time \(\orderle{(lk2^{qs})^c}\), for some constant
\(c\)\@. If \(x\) is accepted by circuit \(C\), then the largest
clique is of size \(k\)\@. If \(x\) is not accepted by circuit \(C\),
then \(T\) is likely to be typical, in which case the largest clique
is of size \(k/2\)\@.
%
\apar{Prove Theorem 2-4}
Assume now that Challenge~2 is true\@. That is, there is an algorithm
that distinguishes between the existence of cliques of size \((\log
n)^{c}\) and the inexistence of cliques of half this size, in time
\(n^{(\log n)^{c(1 -\epsilon)}}\)\@. To check whether the
nondeterministic circuit \(C\) of size \(m\) accepts input \(x\),
apply the reduction above with \(s=m^{1/(c+1)}\)\@. Recall that
\(l=m^{1+\orderlt{1}}\), that \(k=3l/s\), and that
\(q=n^{\orderlt{1}}\)\@. Ignoring \(\orderlt{1}\) factors in the
exponent, we obtain that \(k\simeq m^{c/(c+1)}\) and that the number of
vertices in \(G\) is \(N\simeq k2^{qs}\simeq 2^{m^{1/(c+1)}}\)\@.
Hence \(k\simeq(\log N)^{c}\) (the graph \(G\) can be padded with
dummy vertices to achieve exact equality, if desired)\@. Now the
question of whether \(C\) accepts \(x\) can be decided in randomized
time
\[N^{(\log N)^{c(1-\epsilon)}} 
=2^{m^{1/(c+1)+\orderlt{1}} m^{c(1-\epsilon)/(c+1)+\orderlt{1}}}
=2^{m^{1-c\epsilon/(c+1)}+\orderlt{1}}\]
or in time \(2^{m^{1-\epsilon'}}\),
where \(\epsilon'=c\epsilon/(c+1)+\orderlt{1}\)\@. This proves Goal~2\@.
%
\apar{Prove Theorem 2-5}
To see that Goal~1 follows as well, we use the well known reductions
from randomized algorithms to randomized circuits and from randomized
circuits to nonuniform circuits\@. These reductions result in a
circuit whose size is bounded by a polynomial in the running time of
the original randomized algorithm, and this polynomial overhead is
negligible relative to the superpolynomial complexities involved in
our goals\@.
%
{\nopagebreakbeginpar\markendlst{Proof of Theorem 2}}
\end{alabsubtext}
%
\asection{4}{Discussion}
%
\apar{4-1}
We have seen that if the \(\log\)-Clique problem is in
\(\complexityclass{P}\) (or if the weaker Challenge~2 is met), then
there is subexponential deterministic (or randomized) simulation of
nondeterministic computation\@. We do not wish to take a position
regarding whether our results indicate that finding small cliques is
hard, or that there are subexponential simulations\@. However, we do
wish to point out that the connection between limited nondeterminism
and polynomial nondeterminism suggests that the complexity of problems
such as the \(\log\)-Clique problem is a question worthy of further
research\@.  Hence we discuss our challenges in more detail in
Section~4.2\@.  Before that, in Section~4.1, we make some observations
regarding the motivating goal\@.
%
\asubsection{4.1}{The Significance of our Goal}
%
\apar{4.1-1}
The goal that we consider is that of finding subexponential simulation
for nondeterministic computation\@. This goal came in three different
versions, the uniform one (Question~1), the nonuniform one (Goal~1),
and the randomized one (Goal~2)\@. The uniform version is perhaps the
most appealing\@. The other two versions were introduced so that we
can draw consequences from a challenge that postulates the existence
of an efficient algorithm that (in graphs with small cliques)
approximates the size of the maximum clique within a constant factor,
rather than give its exact size\@. Our reduction in this case is
randomized (specifically, the choice of table \(T\) in Theorem~2), and
we do not know if it can be replaced by a deterministic reduction\@.
%
\apar{4.1-2}
In Goal~1, nondeterministic time is measured as the size of the
nonuniform, nondeterministic circuit family\@. This can be replaced
by other measures of nondeterministic time, provided that
nondeterministic circuit size is at most slightly superlinear in these
measures\@. Pippenger and Fischer~\cite{cj97-01-16} have shown that
there is only a logarithmic blowup when circuits simulate multitape
Turing machines\@. Similarly, the results of Goldreich and
Ostrovsky~\cite{cj97-01-12}, when transformed to a nondeterministic
setting (details omitted), imply that nondeterministic RAMs can be
simulated with polylogarithmic overhead by nondeterministic
circuits\@. (Possibly there is a known simpler proof for this last
fact\@.) Hence, both these measures for nondeterministic time can
replace nondeterministic circuit complexity in Goal~1\@.
%
\apar{4.1-3}
There is a large class of \(\complexityclass{NP}\)-complete problems
for which even if subexponential simulation of
\(\complexityclass{NP}\) is achieved (in the sense of this paper), no
improvement in the known deterministic running time will follow\@.
These problems are those for which the witness length is much shorter
than the input length\@. Typical examples arise in many
graph-theoretic problems, in which the input length depends on the
number of edges, whereas the witness length depends on the number of
vertices\@. For these problems (e.g., the Hamiltonicity, Vertex Cover,
Chromatic Number, and Independent Set problems, all on dense graphs)
it is easy to come up with deterministic algorithms that are
subexponential in the size of the input\@. This reveals two weaknesses
in our notion of subexponential simulation of nondeterminism:
%
\begin{enumerate}
%
\item we do not allow for the possibility of sublinear
nondeterministic running times (at least not for functions that
depend on all their inputs), and
%
\item we do not distinguish between deterministic and nondeterministic
steps of a nondeterministic algorithm, a distinction that exhaustive
search may well take advantage of\@.
%
\end{enumerate}
%
\apar{4.1-4}
Subexponential simulation of nondeterministic computation has
cryptographic significance\@. A persistent trend in cryptography is
to design encryption schemes that are as efficient as possible to
apply (in nearly linear time), and as hard as possible to break
(exponential in the length of the private key)\@. The near-linearity
requirement is important if one must encrypt large volumes of
communication online, using only weak processors\@. The
exponentiality requirement offers security against adversaries who try
to break the encryption scheme offline, using very powerful
computers\@. Goals~1 and~2, if achieved, imply that encryption
schemes with properties as described above do not exist (at least not
in an asymptotic sense, if private keys are long enough)\@. The
complexity of breaking nearly linear encryption schemes would be
subexponential, comparable in nature to the complexity of known
factorization algorithms (see, e.g.,~\cite{cj97-01-10})\@.
%
\asubsection{4.2}{The Plausibility of Our Challenges}
%
\apar{4.2-1}
Challenge~1 calls for efficient algorithms for finding the maximum
cliques in graphs that have small cliques\@. Challenge~2 calls for
approximating the size of the maximum clique within a factor of two\@.
Straightforward probabilistic arguments show that the size of the
maximum clique in almost all graphs is roughly \(2\log n\), and that
simple greedy algorithms find cliques of size roughly \(\log n\) in
almost all graphs\@. Hence for most graphs, Challenge~2 can be met\@.
We do not know if the same holds for Challenge~1\@. This partly
motivates the introduction of Challenge~2\@.
%
\asubsubsection{4.2.1}{Related Work}
%
\apar{4.2.1-1}
Finding small cliques in graphs is a special case of the question of
finding (edge-induced) subgraphs that are isomorphic to other small
subgraphs\@. For some of these subgraphs (e.g., finding a simple path
of length \(\log n\)), Alon, Yuster, and Zwick~\cite{cj97-01-03} give
a polynomial time algorithm, which is much more than we are asking
for\@. The fastest known algorithms for finding subgraphs isomorphic
to a graph \(H\)~\cite{cj97-01-19,cj97-01-03} require time
\(\orderge{n^{t}}\), where \(t\) is the \emph{tree width} of \(H\) (a
notion introduced by Robertson and Seymour~\cite{cj97-01-21})\@.
Unfortunately, the tree width of \(k\)-cliques is \(k-1\)\@.
%
\apar{4.2.1-2}
It is possible to find cliques of size \(k=n-\orderle{\log n}\) in
polynomial time (when they exist)\@. This follows from the fact that
\(k\)-Vertex-Cover has complexity \(\orderle{n^{c}2^{k}}\), and hence
vertex covers of size \(\orderle{\log n}\) can be found in polynomial
time~\cite{cj97-01-20,cj97-01-09,cj97-01-05}\@. To reduce an instance
of the \(k\)-Clique problem to the \(k'\)-Vertex-Cover problem,
simply consider the complement of the input graph, and set
\(k'=n-k\)\@.
%
\apar{4.2.1-3}
For decision problems that involve a parameter (such as in our case,
where the size \(k\) of the clique is a parameter), one can sometimes
design algorithms that have running time \(\orderle{n^{c}f(k)}\), for
some constant \(c\), and arbitrary function \(f\)\@. In this case,
the problem is \emph{fixed-parameter
tractable}~\cite{cj97-01-02,cj97-01-08}, since for every fixed
\(k\), it can be solved in time \(\orderle{n^c}\), where \(c\) is
independent of \(k\)\@. Downey and Fellows~\cite{cj97-01-08}
introduced a hierarchy of fixed-parameter problems, and showed that
the Clique problem is complete for~\(\complexityclass{W}[1]\), the
lowest level of this hierarchy\@. Thus if the Clique problem is not
fixed-parameter tractable, then no problem that is hard for some level
of the hierarchy is fixed-parameter tractable\@. Our techniques allow
us to draw some consequences from the assumption that
the Clique problem is fixed-parameter tractable\@. More
specifically, assume that the \(k\)-Clique problem can be decided in
time \(\orderle{n^{c}f(k)}\), and for simplicity, assume that \(f(k)\)
is a proper complexity function\@. Then for \(k(n)=f^{-1}(n)\),
the \(k(n)\)-Clique problem can be decided in polynomial time\@.
Since \(k(n)\) is not bounded by any constant, a proof similar to that
of Lemma~1 implies that for every \(\epsilon>0\), the Clique problem
can be decided in time \(\orderle{2^{\epsilon n}}\)\@. This implies
similar savings when simulating nondeterministic circuits by
deterministic ones (as in the proof of Theorem~1)\@. We obtain the
following\@.
%
\begin{alabsubtext}{Proposition}{2}{}
%
If the \(k\)-Clique problem (or any other problem that is hard for
the lowest level of the fixed-parameter hierarchy) is
fixed-parameter tractable, then nondeterministic circuits of size
\(NT\) can be simulated by deterministic circuits of size
\(2^{\orderlt{NT}}\)\@.
%
\end{alabsubtext}
%
\apar{4.2.1-4}
We remark that the VC-Dimension problem is contained
in~\(\complexityclass{W}[1]\), and that the Tournament Dominating Set
problem is complete for~\(\complexityclass{W}[2]\), the second level
of the fixed-parameter hierarchy\@. The Monotone Circuit
Satisfiability problem is complete
for~\(\complexityclass{W}[\complexityclass{P}]\), the highest level of
this hierarchy\@. In~\cite{cj97-01-01} it is shown that the class
\(\complexityclass{W}[\complexityclass{P}]\) is fixed-parameter
tractable if and only if satisfiability of a Boolean expression of
size \(m\) on \(n\) variables can be solved in time
\(\polynomial(m)2^{\orderlt{n}}\)\@. This result is of a similar
nature to our Proposition~2\@. It has the advantage of being an ``if
and only if'' connection, and of being able to distinguish between
nondeterministic and deterministic steps in efficiently simulating
nondeterministic computation\@. Proposition~2 has the advantage of
dealing with the lowest level of the fixed-parameter hierarchy\@.
%
\apar{4.2.1-5}
A graph \(H\) is a \emph{minor} of graph \(G\) if a graph isomorphic
to \(H\) can be obtained by contracting edges of a subgraph of
\(G\)\@. By the theory of Robertson and Seymour, for every fixed
\(H\), testing whether \(H\) is a minor of \(G\) can be done in time
\(\orderle{\setsize{V(G)}^{3}}\)~\cite{cj97-01-22}\@. In particular,
testing whether a graph \(G\) has a \(k\)-clique \emph{as a minor} is
fixed-parameter tractable\@.
%
\apar{4.2.1-6}
Papadimitriou and Yannakakis~\cite{cj97-01-20} introduced the class
\(\complexityclass{LOGSNP}\)\@. The problems in this class can be
solved in time \(\orderle{n^{\log n}}\)\@. The \(\log\)-Clique problem
belongs to this class, but is not known to be complete for this class
(see also~\cite{cj97-01-06})\@. Some natural questions, such as the
VC-Dimension and Tournament Dominating Set problems, are
\(\complexityclass{LOGSNP}\)-hard\@. A polynomial time algorithm for
any of these problems implies a polynomial time algorithm for the
\(\log\)-Clique problem; hence, these problems can replace the
\(\log\)-Clique problem in Theorem~1\@.
%
\asubsubsection{4.2.2}{Beating Exhaustive Search}
%
\apar{4.2.2-1}
We survey an approach developed by Itai and Rodeh~\cite{cj97-01-13}
and Nesetril and Poljak~\cite{cj97-01-14} that shows that exhaustive
search is not the quickest way to find cliques\@. Cliques of size
\(3\) can be found quickly by computing \(G^{3}\) (where \(G\) is the
adjacency matrix of the graph) and searching for a nonzero diagonal
entry\@. This requires \(\orderle{n^{\omega}}\) time, where
\(\omega<3\) is the exponent for matrix multiplication (which
currently stands at \(\omega=2.376\)~\cite{cj97-01-07})\@. Cliques of
size \(k\) can be found by finding all \(k/3\)-cliques in the graph
(for simplicity, assume that \(k\) is divisible by \(3\)), then
considering each such \(k/3\)-clique as a vertex in a new larger graph
\(G'\), and connecting two vertices in \(G'\) if together their
corresponding vertices in \(G\) constitute a \(2k/3\)-clique\@. Now
matrix multiplication can be used to find \(3\)-cycles in \(G'\),
leading to an \(\orderle{n^{k\omega/3}}\) algorithm\@.
%
\apar{4.2.2-2}
The natural idea to improve upon the above algorithm is to use
recursion\@. As a first step (one level of recursion), one may try to
find cliques of size \(9\) in \(\orderle{n^{\omega^2}}\) time, or even
just improve upon \(\orderle{n^{3\omega}}\)\@. The problem that one
encounters is that in order to employ the recursion, one needs not
only to determine whether the graph has 3-cycles (which requires
\(\orderle{n^{\omega}}\) time), but also to represent all such
cycles\@. An explicit representation of all these cycles requires
\(\orderge{n^{3}}\) time and space, since the number of \(3\)-cycles
might be as large as \({n\choose 3}\)\@. An implicit representation
may be much shorter (indeed, the graph itself serves as an implicit
representation of all its cycles), but then it is not known how to
perform matrix multiplication on this implicit representation\@.
Thus, finding cliques of size \(9\) efficiently may be the key to the
whole approach\@.
%
\apar{4.2.2-3}
We would like to add here a philosophical remark (the last one)\@.
There is the known association of problems in \(\complexityclass{P}\)
(or in \(\complexityclass{BPP}\)) as tractable, and problems not in
\(\complexityclass{BPP}\) as intractable\@. When asked why an
algorithm of complexity \(n^{13}\) is considered tractable, the usual
answer is that \(n^{13}\) is intractable, but that one almost never
comes up with a polynomial time problem that has this complexity\@.
Is the question of finding cliques of size \(20\) an exception to this
folklore rule\@?
%
\asection{5}{Acknowledgments} 
%
\apar{5-1}
We thank Noam Nisan for pointing out the simple proof of Section~2,
and for allowing us to use it\@. We thank Mike Fellows for useful
references on fixed-parameter tractability, Mihalis Yannakakis for
directing us to~\cite{cj97-01-20}, and Uri Zwick for helpful
discussions\@.
%
\end{articletext}
%
\begin{articlebib}
%
\bibliographystyle{alpha}
\bibliography{cj97-01}
%
\end{articlebib}
%
\end{document}