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 |