Article: 3894 of comp.theory
Xref: crabapple.srv.cs.cmu.edu comp.parallel:3259 comp.theory:3894
Path: crabapple.srv.cs.cmu.edu!pt.cs.cmu.edu!rochester!news.bbn.com!usc!elroy.jpl.nasa.gov!swrinde!gatech!hubcap!dutrun2!hdev@dutiaa.tudelft.nl
From: hdev@ph.tn.tudelft.nl (Hans de Vreught)
Newsgroups: comp.parallel,comp.theory
Subject: Summary: P-complete problems references
Summary: Indeed :-)
Message-ID: <1991Oct23.142747.9897@hubcap.clemson.edu>
Date: 23 Oct 91 14:14:24 GMT
Sender: news@dutrun2.tudelft.nl
Followup-To: comp.parallel
Organization: Clemson University
Lines: 297
Approved: parallel@hubcap.clemson.edu
FIRST PART-----------------------------------------------------------------------
Here is a summary of references on P-complete problems.
Let me first give a (very short) introduction on the subject. P-complete
problems are the hardest problems in P. If it is possible to show that there
exists an efficient parallel algorithm (fast parallel time (=polylog) with a
feasable number (=poly) of processors) for a P-complete problem, then there
exists an efficient algorithm for any problem in P.
If you want to read a survey on the subject in a broader perspective, you
could look in the handbook of TCS:
R.M. Karp, V. Ramachandran, Parallel Algorithms for Shared-Memory
Machines, in: Handbook of Theoretical Computer Science, Volume A.,
1990.
It's probably not the best survey on the subject, but your library has the
handbook (and in most libraries handbooks may not be lent out). However there
are many references in it.
If you want to have a good text BOOK on the subject, you should read the last
chapter of the excellent book:
A. Gibbons, W. Rytter, Efficient Parallel Algorithms, 1988.
It discusses (with proofs) a set of P-complete problems which can be used for
proving that other problems are P-complete. It is a bit like the early chapters
of Garey & Johnson (but smaller): proving NP-completeness of SAT, 3SAT, VC,
HAMC, TSP, etc.
The following articles give lists of problems known to be P-complete:
* N.D. Jones, W.T. Laaser, Complete Problems for Deterministics
Polynomial Time, TCS 3: 105-117, 1977.
This is a real well known article. It's readable.
* J. Avenhaus, K. Madlener, The Nielsen Reduction and P-complete Problems
in Free Groups, TCS 32: 61-76, 1984.
* J.S. Vitter, R.A. Simons, New Classes for Parallel Complexity: A Study
of Unification and Other Complete Problems for P, IEEE Trans. on Comp.
Vol. C-35, 5: 403-418, 1986.
Now for the big work. There are two reports you need to have:
* R. Greenlaw, H.J. Hoover, W.L. Ruzzo, A Compendium of Problems
Complete for P, Univ. of Alberta, CS, TR 91-11, 1991.
The authors are currently updating this report and hope to finish it in
the near future:
* If you know a new P-complete problem you are invited to send
it to them.
* THEY WANT TO MAKE A MAILING LIST TO PEOPLE THAT WANT TO HAVE
THE UPDATED REPORT, SO THAT THEY CAN SEND ANNOUNCEMENTS TO.
Their addresses are:
* hoover@cs.ualberta.ca
* ruzzo@cs.washington.edu
* greenlaw@unh.edu
The report is just like Garey & Johnson; first some theory (41 pages)
and then a list of 96 P-complete problems.
* S. Miyano, S. Shiraishi, T. Shoudai, A List of P-complete Problems,
Kyushu University, RIFIS-TR-CS-17, 1990.
The authors of this report promise to revise the list on a yearly
basis, and new P-complete problems should be sent to:
* miyano@rifis.sci.kyushu-u.ac.jp
The theory is cut back to just 9 pages and is followed by 91 P-complete
problems.
Both reports of course have quite an extensive bibliography on the subject.
Acknowledgements:
I am especially grateful to Larry Ruzzo for his time and effort, for helping me
ftp his report, for sending a report, etc. Thanks. I also like to thank Jim
Hoover and all the others who helped me by contributing to this summary.
--
Hans de Vreught - hdev@dutiaa.tudelft.nl
Delft University of Technology (TWI-ThI)
P.S.
In the summary below I have maid some some changes, deleted some line, etc.
Remarks between '{' and '}' are mine.
THE SECOND PART------------------------------------------------------------------
From: sarnath@cs.Buffalo.EDU (Ramnath Sarnath)
" A P-complete Graph Partition Problem" - R. Sarnath and X. He.
Theoretical Computer Science, 76, 1990, 343-351.
We have another 5 references in there. Also look at a paper by Jones
and Laaser , Theoret Comp. Sc., 3, 1977, 105-117.
Also Dobkin et al, Information Proc. letters, 8, 1979, 96-97.
---------------------------------------------------------------------------------
From: bach@cs.wisc.edu (Eric Bach)
{No reference, but a very useful email address! Thanks Eric.}
---------------------------------------------------------------------------------
From: lane@cs.rochester.edu (Lane Hemachandra)
Hi! I know of two fine collections of P-complete problems, one done by
greenlaw@titleist.cs.unh.edu (and his coauthors)
and one done by
miyano@rifis.sci.kyushu-u.ac.jp (and his coauthors).
---------------------------------------------------------------------------------
From: vavasis@cs.cornell.edu (Stephen Vavasis)
``Gaussian elimination with pivoting is P-complete,'' S. A. Vavasis,
SIAM J. Discr. Math, 2 (1989) 413-423.
This paper shows that the problem of computing the sequence of
pivots used by Gaussian elimination with partial or complete
pivoting (the standard numerical algorithms for solving unstructured
linear systems) is P-complete.
---------------------------------------------------------------------------------
From: samir@umiacs.UMD.EDU (Samir Khuller)
Samir Khuller, ``On Computing Graph Closures'',
{\em Information Processing Letters} 31 (5) (1989) pp. 249--255.
The most well known one is perhaps by Goldschlager, Shaw and Staples on max-
flow. {L. Goldschlager, L. Shaw, J. Staples, The maximum flow problem is log
space complete for P, TCS 21: 105-115, 1982.}
---------------------------------------------------------------------------------
From: Hans de Vreught {That's me}
Some problems can also be found in the textbooks:
* M.R. Garey, D.S. Johnson, Computers and Intractability, 179ff.
* J.E. Hopcroft, J.D. Ullman, Introduction to Automata Theory,
Languages and Computation, 347ff.
* R. Sommerhalder, S.C. van Westrhenen, The Theory of Computability,
384ff.
But these books only treat P-complete problems as a related subject.
---------------------------------------------------------------------------------
From: ros@cs.pitt.edu (Hans Ros)
The following article contains log**k space reductions, for k>=1
{translated to English, original was in Dutch}.
"Complete problems for deterministic polynomial time", Neil D. Jones,
William T. Laaser, STOC 1974, pp 40-46. {Preliminary version of the one
that appeared in TCS; see first part of my article}
---------------------------------------------------------------------------------
From: achin@math.tamu.edu (Andrew Chin)
Jacobo Toran (U. Politecnica de Cataluna) has written a review paper for
ALCOM Spring School on Parallel Computation, to appear in Cambridge U. Press
(A. Gibbons & P. Spirakis, eds.)
Two surveys of P-complete problems:
Raymond Greenlaw, H. James Hoover and W. Larry Ruzzo, ``A compendium of
problems complete for P,'' Tech Report, U. of Washington (2 parts).
Satoru Miyano, Shuji Shiraishi and Takayoshi Shoudai, ``A list of P-complete
problems,'' Tech Report, Research Institute of Fundamental Information Science,
Kyushu University 33, Fukuoka, Japan.
---------------------------------------------------------------------------------
From: Larry Denenberg
Here are a few. First of all, satisfiability of CNF-1 formulas (formulas
of pure quantificational theory whose matrices are conjunctions of atomic
formulas and negations of atomic formulas) is complete for P; this follows
from work in Kannellakis, Dwork, and Mitchell, "On the sequential nature
of unification," J. Logic Programming vol 1 (1984). Satisfiability of
monadic CNF-2 (aka Krom) formulas is also P-complete as shown in Denenberg
and Lewis, "Complexity of the satisfiability for Krom formulas,"
Theoretical Comp. Sci. vol 30 (1984).
A "multivalued dependency" is a particular kind of relational database
constraint: if X and Y are disjoint sets of attributes, the multivalued
dependency X->->Y means that the database is the join of its projections
on (X union Y) and on (U minus Y), where U is the set of all attributes of
the database. The inference problem for multivalued dependencies (given a
set of such dependencies, to determine whether they imply another given
dependency) is proved P-complete in Denenberg, "Computational complexity
of logical problems," Ph. D. Thesis, Harvard University (1984).
If you don't already have it, check out Jones and Laaser, "Complete problems
for deterministic polynomial time," Theoretical Comp. Sci. vol 3 (1976).
Among others, the inference problem for propositional Horn formulas is there
proved P-complete.
---------------------------------------------------------------------------------
From: Larry Ruzzo
{Essentially the one below}
From: Jim Hoover
The latest version of our P-complete reference, dated July 1991
can be obtained by anonymous ftp from me. The information follows
my signature. {removed} We are curently working on the next version, so the
distribution of this version should be minimized.
A Compendium of Problems Complete for P
Version 0 -- 1991 July 10
Raymond Greenlaw (1),
H. James Hoover (2),
Walter L. Ruzzo (3)
Department of Computing Science
University of Alberta
Technical Report TR 91--11
Department of Computer Science and Engineering
University of Washington
Technical Report TR 91--05--01
Abstract:
This paper serves two purposes. Firstly, it is an elementary
introduction to the theory of P completenessness --- the branch of
complexity theory that focuses on identifying the problems in the
class P that are ``hardest'', in the sense that why they appear
to lack highly parallel solutions.
That is, they do not have parallel solutions using time polynomial
in the logarithm of the problem size and a polynomial number of
processors unless all problem in P have such solutions, or equivalently,
unless P=NC.
Secondly, this paper is a reference work of P-complete problems.
We present a compilation of the known P-complete problems,
including several unpublished or new P-completeness results,
and many open problems.
This document is available in electronic form by anonymous ftp from
..X.-.R.A.Y.E.D...{see first part article}.. as either a compressed
dvi file (TR91-11.07-10.dvi.Z) or as a compressed postscript file
(TR91-11.07-10.ps.Z).
Because this document is constantly being expanded, the latest version
can usually be found in TR91-11.dvi.Z and TR91-11.ps.Z .
(1) Department of Computer Science,
University of New Hampshire, Durham, NH 03824,
e-mail address: greenlaw@unh.edu
(2) Department of Computing Science,
University of Alberta, Edmonton, Alberta, Canada T6G~2H1,
e-mail address: hoover@cs.ualberta.ca
(3) Department of Computer Science and Engineering, FR-35,
University of Washington, Seattle, WA 98195,
e-mail address: ruzzo@cs.washington.edu
---------------------------------------------------------------------------------
From: Larry Ruzzo
{A respons on a email from me to Larry after ftp'ing his report.}
Thanks. I hope you find it useful. You'll definitely find some
rough edges, not to mention outright errors, in the version you got,
so proceed with caution. Feel free to mention it & give my email
address in your summary to the net, but due to the above, and given
that we should have a much more polished version available in a few
weeks, I guess my preference would be to not widely broadcast the
ftp instructions at this time. You might also include mention of
another survey in the same area, somewhat shorter, but nicely done.
@techreport(MiShSh,
author="Miyano, S. and Shiraishi, S. and Shoudai, T.",
title="A List of {$P$}-Complete Problems",
year=1989,
institution="Kyushu University 33, Research Institute of Fundamental
Information Science",
number="RIFIS-TR-CS-17",
note={Revised Dec 29,1990, 68 pages.})
---------------------------------------------------------------------------------
From: Jim Hoover
Please do mention our email addresses, we are compiling a list of people
that we can send announcements to.
---------------------------------------------------------------------------------
From: Sven-Olof Nystr|m
{I wrote:}
>Sven-Olof Nystr|m writes:
>> Subject: P-complete references wanted
>>
>> I have on my desk an article named "The complexity of parallel algorithms".
>> It contains a good introduction and plenty of references.
>> Author is Richard Anderson at Stanford University. I do not have the year
>> of
>> publication but from the references I figure it is between 1985 and 1989.
>>
>Is this his PhD Thesis (or its summary)?
> R.J. Anderson, The complexity of parallel algorithms", PhD Thesis,
> Stanford University, TR STAN-CS-86-1092, 1985.
>If not can you determine the periodical in which it appeared?
>
>
>--
>Hans de Vreught
>
>
All I have is a xerox copy of the article and there is no explicit details
about
when or as what it has been published. However, it seems to be published by
Stanford University, and yes, it looks like a PhD thesis (69 pages, long
introduction). The abstract begins "This thesis ..." so I guess probably is
a PhD thesis.
---------------------------------------------------------------------------------
From: Kallol Kumar Bagchi
A general discussion on P-complete ones is in Gibbons and Rytter,chapter 7,
Efficient Parallel Algorithms,Cambridge University Press,88 {corrected}.
---------------------------------------------------------------------------------
Article 4131 of comp.theory:
Newsgroups: comp.theory
Path: crabapple.srv.cs.cmu.edu!cantaloupe.srv.cs.cmu.edu!rochester!news.bbn.com!usc!zaphod.mps.ohio-state.edu!van-bc!ubc-cs!alberta!hoover
From: hoover@cs.UAlberta.CA (Jim Hoover)
Subject: P-complete Compendium
Message-ID: <1991Dec28.185137.22715@cs.UAlberta.CA>
Sender: news@cs.UAlberta.CA (News Administrator)
Nntp-Posting-Host: swanhills.cs.ualberta.ca
Organization: University of Alberta
Date: Sat, 28 Dec 1991 18:51:37 GMT
Dear Colleagues:
The latest version of Part II of our P-complete Compendium is now available.
This contains the Contents, Problem List, References, and Index. We are
currently revising Part I (the theory) and plan to have it ready in the new
year.
OBTAINING A COPY:
You have three options for obtaining a copy of this version.
1. The simplest is to ftp from alberta or washington. See the last paragraph
of the abstract for details. Compressed dvi and postscript are available.
NOTE: as of this posting, ftp from washington is not yet possible.
2. For those without ftp access, email a request to hoover@cs.ualberta.ca with
the subject of "P-complete: email me dvi", or "P-complete: email me postscript".
You will be sent a number of uuencoded files which can be combined to
produce the requested format.
3. The slowest method is to email or mail a request to hoover@cs.ualberta.ca
for a paper copy. Since the full paper is over 100 pages long, it is quite
expensive to produce and distribute paper versions, so please use this option
only if you have no alternative.
For options 2 and 3, please include the same information as requested for
database additions below.
READER DATABASE:
We are also maintaining a database of those who wish to be informed of
updates. To be added to the database, send a message to hoover@cs.ualberta.ca
with the subject of "P-complete: add me", and have the initial lines of the
body of your message as follows:
your name
your email address
your physical mail address
After that you can include a note as to whether you can ftp or not. There are
already a number of entries in the database. If you are in the database you
will be receiving a message to that effect in the next few days. If you think
you are in the database and don't get a message, send an "add me" message.
ABSTRACT:
A Compendium of Problems Complete for P
December 20, 1991
RCS Revision: 1.46
Abstract
This paper serves two purposes. Firstly, it is an elementary introduction
to the theory of P-completeness --- the branch of complexity theory that
focuses on identifying the problems in the class P that are ``hardest,''
in the sense that they appear to lack highly parallel solutions. That is,
they do not have parallel solutions using time polynomial in the logarithm
of the problem size and a polynomial number of processors unless all problems
in P have such solutions, or equivalently, unless P=NC. Secondly, this
paper is a reference work of P-complete problems. We present a compilation
of the known P-complete problems, including several unpublished or new
P-completeness results, and many open problems.
This is a PRELIMINARY version, mainly containing the problem list. The
latest version of this document is available in electronic form by anonymous
ftp from thorhild.cs.ualberta.ca (129.128.4.53) as either a compressed dvi
file (pub/TR91-11.dvi.Z) or as a compressed postscript file (pub/TR91-11.ps.Z),
or from cs.washington.edu (128.95.1.4) as a compressed postscript file
(tr/1991/05/uw-cse-91-05-01.ps.Z).
Authors' addresses:
Raymond Greenlaw
Department of Computer Science,
University of New Hampshire, Durham, NH 03824
e-mail address: greenlaw@unh.edu
H. James Hoover
Department of Computing Science,
University of Alberta, Edmonton, Alberta, Canada T6G 2H1,
e-mail address: hoover@cs.ualberta.ca
Walter L. Ruzzo
Department of Computer Science and Engineering, FR-35,
University of Washington, Seattle, WA 98195,
e-mail address: ruzzo@cs.washington.edu
Technical report numbers:
Department of Computing Science
University of Alberta
Technical Report TR 91--11
Department of Computer Science
University of New Hampshire
Technical Report TR 91--14
Department of Computer Science and Engineering
University of Washington
Technical Report TR 91--05--01
--
Prof. Jim Hoover | Office +1 403 492 5401 or 5290
Dept. of Computing Science | FAX +1 403 492 1071
University of Alberta | hoover@cs.ualberta.ca
Edmonton, Alberta, Canada T6G 2H1 |