On the complexity of unique solutions

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the complexity of unique solutions

Full text

Pdf (433 KB)

Source

Journal of the ACM (JACM) archive
Volume 31 , Issue 2 (April 1984) table of contents

Pages: 392 - 400

Year of Publication: 1984

ISSN:0004-5411

Author

Christos H. Papadimitriou

Department of Computer Science, Stanford University, Stanford, CA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 60, Citation Count: 11

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/62.322435 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
	2	F'RAENKEL, A. S., GAREY, M. R., JOHNSON, D. S., SHAEFER, T. J., and YESHA, Y.Theom#exity of checkers on an n x n board, in Proceedtngs of the 19th Foundattons of Computer Science IEEE, New York, 1978, pp. 55-64.
	3	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	4	GAREY, M. R., JOHNSON, D. S., and TAP, JAN, R. E.The planar Hamiltonian circuit problem is NP-complete. SlAM ~ Comput. 5, 4 (1976), 704-714.
	5	ITAI, A., PAPADIMITRIOU, C. H., and SZWARCFITER, J. L.Hamilton paths in grid graphs. SlAM ~ Comput. 10, 4 (1981).
	6	KARP, R. M.Reproducibility among combinatorial problems. In Complexity of Computer Compumtions, R. E. Miller and J. W. Thatcher, Eds. Plenum Press, New York, 1972, pp. 85-103.
	7	LICHTENSTEIN, D., AND SIPSER, M. Go is PSPACE-hard. In Proceedings of the 19th Foundations of Computer Saence. IEEE, New York, 1978, pp. 48-54.
	8	PAPADIMITRIOU, C. H.The adjacency relation on the travelling salesman problem polytope is NP- complete. Math Program 14 (1978), 312-324.
	9	Christos H. Papadimitriou , Paris C. Kanellakis, Flowshop scheduling with limited temporary storage, Journal of the ACM (JACM), v.27 n.3, p.533-549, July 1980 [doi>10.1145/322203.322213]
	10	Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
	11	C. H. Papadimitriou , M. Yannakakis, The complexity of facets (and some facets of complexity), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.255-260, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802199]
	12	SCHAEFER, T.J.complexity of some two-person perfect information games. Z Comput Syst Sci. 16 (1978), 185-225.
	13	L. J. Stockmeyer , A. R. Meyer, Word problems requiring exponential time(Preliminary Report), Proceedings of the fifth annual ACM symposium on Theory of computing, p.1-9, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804029]

CITED BY 11

	Edith Hemaspaandra , Lane A. Hemaspaandra , Jörg Rothe, Exact analysis of Dodgson elections: Lewis Carroll's 1876 voting system is complete for parallel access to NP, Journal of the ACM (JACM), v.44 n.6, p.806-825, Nov. 1997
	Thomas Eiter , Georg Gottlob , Heikki Mannila, Disjunctive datalog, ACM Transactions on Database Systems (TODS), v.22 n.3, p.364-418, Sept. 1997
	Friedhelm Meyer auf der Heide, Fast algorithms for N-dimensional restrictions of hard problems, Journal of the ACM (JACM), v.35 n.3, p.740-747, July 1988
	F. Laroussinie , N. Markey , Ph. Schnoebelen, Efficient timed model checking for discrete-time systems, Theoretical Computer Science, v.353 n.1, p.249-271, 14 March 2006
	Nicola Leone , Gerald Pfeifer , Wolfgang Faber , Thomas Eiter , Georg Gottlob , Simona Perri , Francesco Scarcello, The DLV system for knowledge representation and reasoning, ACM Transactions on Computational Logic (TOCL), v.7 n.3, p.499-562, July 2006
	André Große , Jörg Rothe , Gerd Wechsung, On computing the smallest four-coloring of planar graphs and non-self-reducible sets in P, Information Processing Letters, v.99 n.6, p.215-221, 30 September 2006
	Simona Perri , Francesco Scarcello , Nicola Leone, Abductive logic programs with penalization: semantics, complexity and implementation, Theory and Practice of Logic Programming, v.5 n.1-2, p.123-159, January 2005
	Hana Chockler , Joseph Y. Halpern , Orna Kupferman, What causes a system to satisfy a specification?, ACM Transactions on Computational Logic (TOCL), v.9 n.3, p.1-26, June 2008
	Hana Chockler , Ofer Strichman, Before and after vacuity, Formal Methods in System Design, v.34 n.1, p.37-58, February 2009
	Hana Chockler , Joseph Y. Halpern, Responsibility and blame: a structural-model approach, Proceedings of the 18th international joint conference on Artificial intelligence, p.147-153, August 09-15, 2003, Acapulco, Mexico
	Hana Chockler , Joseph Y. Halpern, Responsibility and blame: a structural-model approach, Journal of Artificial Intelligence Research, v.22 n.1, p.93-115, July 2004