Announcing . . .

Our book is now available. Cost is around $55.00 US.

Excerpts

The following are excerpts from the book. All material is copyright Oxford University Press.

• LaTeX .dvi versions
• Table of Contents
• Preface
• Chapter 1: Introduction
• Problem List
• Index
• or All of the above
• PostScript versions
• Table of Contents
• Preface
• Chapter 1: Introduction
• Problem List
• Index
• or All of the above
• Ftp Access You can examine the above excerpt by

        ftp ftp.cs.ualberta.ca
        cd pub/hoover/P-complete

and getting any one of

        excerpt.dvi
        excerpt.dvi.Z
        excerpt.ps
        excerpt.ps.Z

Errata and Additions - Last Update 1997 February 04

The following significant errors have been detected so far:

1. None.

The following minor errors have been detected so far:

1. Luca Trevisan of Universita' degli Studi di Roma noted that in A.4.1 Linear Inequalities, page 150 line -5, the remarks on restricting entries to {0, 1} should be to {-1, 0, 1}. Luca also observed that when A and b have nonnegative entries the problem is in NC, as per the following algorithm sketch:

First, if there is a feasible x then there is a feasible x that has at most 1 nonzero entry. This is because all the inequalities point to the left and x > 0.

In parallel, solve d separate instances by plugging in 0's for all but one of the values. What we are left with after matrix multiplying is some inequalities with only one variable remaining. Things like c * x_i <= b_i for some number c. Now see if there is a positive x satifying the tightest constraint. If any of the d instances can be solved, then the original can be.

2. For clarity, in A.4.3 Linear Programming, page 151 line -7 insert the word feasible before x'.
3. Eric Allender at Rutger's pointed out that in appendix D.2 Relationships Among Complexity Classes, page 254 line -5, that the correct containment is

        NLOG contained in DET
        NLOG contained in AC^1

It is open if DET is contained in AC^1. For a good table of the various relationships, check out David Johnson's A catalog of complexity classes, in the Handbook of Theoretical Computer Science, Volume A, edited by J. van Leeuwen.

4. Loren Schwiebert of Wayne State University points out that on Page 54, Section 3.4.2 we state that the question of whether or not P = POLYLOGSPACE is unresolved. Garey and Johnson, pg. 181, remark that Ron Book showed that P =/= POLYLOGSPACE. So it would be more precise to say that the relationship between P and POLYLOGSPACE is not known.
   Book, R. V. "Translational lemmas, polynomial time, and (log n)^j-space", Theoretical Computer Science 1, 215-226 (1976).

The following silly errors have been detected so far:

1. In the index, the page entry for the standard encoding should be 29 not 79.
2. We botched title page and neglected to supply our institutions on the cover page of the book.
3. Compounding this error, the Authors' Addresses page (below) was ommitted from the printing!
4. On Page 21 Line 19, "chose" should be "choose".

At some point in the future this section will enable you to obtain updates and to submit errors and new problems.

Solved Open Problems - Last Update 1995 September 07

The following problems are no longer open:

B.4.1 Strong Bisimilarity in Deterministic Transition Systems (SBDTS)

(Pointed out by Sandeep Shukla.) A NC algorithm for this can be found in Dung T. Huynh and Lu Tian, On deciding some equivalences for concurrent processes. in Theoretical Informatics and Applications, 28(1):51-71,1994. They show that trace equivalence for deterministic transition systems is NL-complete, and thus in NC.

A different approach can be found in Sandeep K. Shukla, Daneil J. Rosenkrantz, Harry B. Hunt III, S. S. Ravi, and R. E. Stearns. (Preprint, contact sandeep@cs.albany.edu). They reduce the problem to 2SAT.

That 2SAT is in NC follows from Jones, Lien, and Laaser (Mathematical Systems Theory, 10, 1976) (? title to be looked up), where they show 2CNF Unsatisfiability is in NL. Then the Immerman/Solipinski result (Reference here?) that NL is closed under complementation yields 2SAT in NL and thus in NC.

Here is a sketch of an NC algorithm for 2SAT (a common homework problem).

Other Problems - Last Update 1997 February 04

The following problems are new P-complete problems, or additional remarks.

1. Majority-Vote Cellular Automata, Ising Dynamics, and P-Completeness

   Cristopher Moore (submitted to the Journal of Statistical Physics)

   We study cellular automata where the state at each site is decided by a majority vote of the sites in its neighborhood. These are equivalent, for a restricted set of initial conditions, to non-zero probability transitions in single spin-flip dynamics of the Ising model at zero temperature.

   We show that in three or more dimensions these systems can simulate Boolean circuits of AND and OR gates, and are therefore P-complete. That is, predicting their state t time-steps in the future is at least as hard as any other problem that takes polynomial time on a serial computer.

   Therefore, unless a widely believed conjecture in computer science is false, it is impossible even with parallel computation to predict majority-vote cellular automata, or zero-temperature single spin-flip Ising dynamics, qualitatively faster than by explicit simulation.

   Click here to download. Author's address: Cris Moore <moore@santafe.edu>

2. Circuits and Expressions with Non-Associative Gates

   Joshua Berman, Arthur Drisko, Francois Lemieux, Cris Moore, and Denis Therien

   You can obtain it from ftp://ftp.santafe.edu/pub/moore/circuits.ps or http://www.santafe.edu/~moore We consider circuits and expressions whose gates carry out multiplication in a non-associative algebra such as a quasigroup or loop. We define a class we call the {\em polyabelian} algebras, formed by iterated quasidirect products of Abelian groups. We show that a quasigroup can express arbitrary Boolean functions if and only if it is not polyabelian, in which case its {\sc Expression Evaluation} and {\sc Circuit Value} problems are NC^1-complete and P-complete respectively. This is not true for algebras in general, and we give a counter-example. We show that {\sc Expression Evaluation} is also NC^1-complete if the algebra has a non-solvable multiplication group or semigroup, but is in TC^0 if the algebra is both polyabelian and has a solvable multiplication semigroup, e.g. for a nilpotent loop or group. Thus, in the non-associative case, earlier results about the role of solvability in circuit complexity generalize in several different ways. Cris Moore moore@santafe.edu http://www.santafe.edu/~moore

Authors' Addresses

Raymond Greenlaw
Department of Computer Science
Armstrong Atlantic State University
11935 Abercorn Street
Savannah, Georgia 31419-1997, U.S.A.
e-mail address: greenlaw@pirates.armstrong.edu
world wide web: http://www.cs.armstrong.edu/greenlaw

H. James Hoover
Department of Computing Science
University of Alberta
Edmonton, Alberta, T6G 2H1, Canada
e-mail address: hoover@cs.ualberta.ca
world wide web: http://www.cs.ualberta.ca/~hoover

Walter L. Ruzzo
Department of Computer Science and Engineering, FR-35
University of Washington
Seattle, WA 98195, U.S.A.
e-mail address: ruzzo@cs.washington.edu
world wide web: http://www.cs.washington.edu/homes/ruzzo

Change Log:

1994-Dec-12 - In Preface - Changed Authors' and book World Wide Web addresses.
1994-Apr-24 - Book is now available.
1995-Sep-20 - Added open problems and errors section.
1996-June-11 - Updated errata section.
1996-June-27 - Updated Greenlaw's URL.
1996-Sept-10 - Added new problems section.
1997-Feb-04 - Layout adjustments, link to Oxfird. Added minor error 4. Added other problem 2.
1998-Sept-29 - Changed Greenlaw's address