FALSE. The standard non-regular language, {anbn: n &ge 0}, is decidable in logspace. You count the a's with a binary counter, count the b's with a binary counter, and compare the answers (after first checking that the input is in a*b*). A binary counter that goes up to n can be kept on a tape in O(log n) space.
FALSE. Becky showed us two examples of NP-complete optimization problems that could be approximated to within a factor of two: the MAX-CUT maximization problem and the MIN-VERTEX-COVER minimization problem.
TRUE. NPA is the class of languages of poly-time NDTM's with access to an oracle for A. If such a machine does not use its nondeterminism, it is a poly-time DTM with access to an oracle for A, which is exactly what decides an arbitrary language in PA.
TRUE. An RP algorithm cannot accept if the input is not in its language, and accepts with probability at least 1/2 if the input is in its language. It thus is already an NP algorithm for the same language, as it can accept the input iff the input is in its language.
TRUE. A machine with an O(log n) space bound has only polynomially many possible configurations (2O(log n) times other terms that are all polynomial). If it runs for longer than its number of configuration, it must be in a loop, since it is deterministic. So if we add a clock that rejects after it runs this long, it accepts the same language as before and is now a poly-time machine. Its language is thus in P.
FALSE. We saw in lecture that TQBF, the set of true quantified boolean formulas, is complete for PSPACE under P-reductions. It is in PSPACE because we can search the entire tree of possible settings to the variables using PSPACE (the depth of this tree is bounded by the input size). An arbitrary language in PSPACE can be decided by reference to the PATH problem on the exponential-sized configuration graph. By the Savitch algorithm we can write a poly-length quantified boolean formula that is true iff the path in question exists, thus reducing the original question to a TQBF question. (I would give eight points out of ten for only the first sentence of this answer.)
FALSE. 2-SAT is in P without any conditions. We can make a graph of the literals in the 2-SAT formula, interpret each clause as a pair of implications, represent these implications as edges, and determine whether a contradiction exists by repeated PATH questions on the resulting directed graph. The PATh problem on a poly-size graph is in NL and therefore in P.
In each case we can guess a polynomial-sized string y such that x is in our language iff a P-testable property holds for x and y. In the case of CLIQUE y is a clique of size k -- it is easy in P to test whether a given set has size k and is a clique in a given graph. In the case of HALF-CLIQUE y is a clique of size n/2 -- in the same way given a graph and a set we can test in P whether the set is a clique. In the case of FULL-CLIQUE we could argue the same way (choose a set of size n) but since there is only one set of size n we see that this language is actually in P as well as being in NP.
We showed above (#9) that HALF-CLIQUE is in NP, so it remains to reduce a
known NP-complete language to HALF-CLIQUE. It is suggested that we use
CLIQUE, meaning that we need a map from pairs (G,k) to graphs H such that G
has a clique of size k iff H has a clique of size n/2 (where n, an even
number, is the number of nodes in H). We don't want to delete anything from
G as we make H, because any part of G might be important in forming a clique
of size k. So we will make H by adding nodes to G. Let m be the number of
nodes in G.
If k &ge m/2, we can make H equal to G plus some number t of new nodes
of degree 0. Then G has a clique of size k iff H has a clique of size k.
We get the desired reduction by making the size of H, n=m+t, exactly 2k, so
that k=n/2. This can be done my making t = 2k - m, which is possible
whenever k &ge m/2.
If k < m/2 we need a different construction. Again we add t new nodes,
but now we also add edges from each new node to each other node in the graph,
both new and node. Thus any k-clique in G combines with the t new nodes
to make a (k+t)-clique in H. (And a k+t size clique in H must include at
least k old nodes, which form a clique in G.) So we need only pick t such
that k+t = (m+t)/2, or t = m-2k, so that the cliques we seek in H are
exactly size n/2.
old
FULL-CLIQUE is in P, because we need only check each of the (n choose 2) possible edges and accept iff all of them are edges. If FULL-CLIQUE were NP-complete as well as being in P, every language in NP would be P-reducible to a language in P and thus be in P itself. P would then equal NP, contradicting the assumption.
The input graph is in FULL-CLIQUE iff all of the (n choose 2) possible edges are present. This is the AND of (n choose 2) conditions, each of which can be tested by looking at one bit of the input (if the graph is given as an adjacency matrix). We can build a circuit consisting of one AND gate of fan-in (n choose 2), with these edge tests at its inputs. This circuit has depth 1, which is O(1), unbounded fan-in, and size (n choose 2), which is polynomial in n. The language is thus in AC^0.
A language A is NL-complete under logspace reductions iff (a) A is in NL, and (b) for any language B in NL, there exists a function f, computable in logspace, such that for any string x, x is in B iff f(x) is in A.
The language PATH, consisting of all triples (G,s,t) such that G is a directed
graph, s and t are nodes in G, and there exists a path from s to t in G, is
NL complete under logspace reductions. For condition (a) from #13, we note
that PATH is in NL by the "blundering algorithm". This sets a pointer to s,
repeatedly changes the pointer by following an edge out of the current
location, and accepts iff the pointer ever becomes t. This is a correct
nondeterministic procedure for PATH because it can accept iff the input is in
PATH. It is implementable in O(log n) space because each pointer takes up
only O(log n) bits.
For condition (b), let B be an arbitrary NL language and let M be the
logspace NDTM that can accept x iff x is in B. Our input f(x) to PATH will
be (G,s,t), where G is the configuration graph of M on x, s is the start node
of this graph, and t is the accept node. The configuration graph of M on x
has a node for each possible configuration (state, tape head positions, and
tape contents) and an edge from node u to node v iff v represents a
configuration reachable from u in one step according to the rules of M and
the input x. The graph is buildable in logspace because we can use a
poly-sized loop (with index in O(log n) bits) to produce each configuration
in alphabetical order, and then produce the adjacency matrix by two nested
loops. These latter loops consider every pair of configurations and examine
them to see whether one is reachable in one step from the other -- this last
is a logspace operation.
Last modified 8 May 2001