Nothing Special   »   [go: up one dir, main page]

skip to main content
10.1145/800076.802476acmconferencesArticle/Chapter ViewAbstractPublication PagesstocConference Proceedingsconference-collections
Article
Free access

Low level complexity for combinatorial games

Published: 11 May 1981 Publication History

Abstract

There have been numerous attempts to discuss the time complexity of problems and classify them into hierarchical classes such as P, NP, PSPACE, EXP, etc. A great number of familiar problems have been reported which are complete in NP (nondeterministic polynomial time). Even and Tarjan considered generalized Hex and showed that the problem to determine who wins the game if each player plays perfectly is complete in polynomial space. Shaefer derived some two-person game from NP complete problems which are complete in polynomial space.
A rough discussion such as to determine whether or not a given problem belongs to NP is independent of the machine model and the way of defining the size of problems, since any of the commonly used machine models can be simulated by any other with a polynomial loss in running time and by no matter what criteria the size is defined, they differ from each other by polynomial order. However, in precise discussion, for example, in the discussion whether the computation of a problem requires O(n k) time or O(nk+l) time, the complexity heavily depends on machine models and the definition of size of problems. From these points, we introduce somewhat stronger notion of the reducibility.

References

[1]
Chandra, A. K. and L. Stockmeyer, Alternation, 17 th Annual Symposium on Foundations of Computer Science, 1976, 98-108
[2]
Chandra, A. K., D. C. Kozen and L. Stockmeyer, Alternation, Research Report IBM Thoms J. Watson Research Center, RC 7489, 1978
[3]
Cook, S. A., Characterizations of Pushdown machines in terms of time bounded computers, JACM 18, 1971
[4]
Hopcroft, J. E. and J. D. Ullman, Introduction to Automata theory, Languages, and Computation, Addison Wesley, Reading, Mass., 1979
[5]
Kasai, T.,A. Adachi and S. Iwata, Classes of Pebble games and Complete Problems, SIAM J. on Comput., Vol. 8, No 4, 1979
[6]
Stockmeyer, L., Classifying the Computational complexity of problems, Research Report RC 7606, IBM Watson Research Center, 1979(also in Proc. of the second IBM Symp. on Mathematical Foundation of Computer Science, 1977)
[7]
Stockmeyer, L. and A. K. Chandra, Provably difficult combinatorial games, Research Report RC 6597, IBM Thomas J. Watson Research Center, 1978

Cited By

View all
  • (2006)Logical syntax and computational complexityComputation and Proof Theory10.1007/BFb0099481(101-115)Online publication date: 15-Nov-2006
  • (1987)Are problems having a polynomial time upper bound actually thought to be feasible?Discrete Algorithms and Complexity10.1016/B978-0-12-386870-1.50023-X(311-324)Online publication date: 1987

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
STOC '81: Proceedings of the thirteenth annual ACM symposium on Theory of computing
May 1981
390 pages
ISBN:9781450373920
DOI:10.1145/800076
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 May 1981

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Article

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)38
  • Downloads (Last 6 weeks)11
Reflects downloads up to 21 Nov 2024

Other Metrics

Citations

Cited By

View all
  • (2006)Logical syntax and computational complexityComputation and Proof Theory10.1007/BFb0099481(101-115)Online publication date: 15-Nov-2006
  • (1987)Are problems having a polynomial time upper bound actually thought to be feasible?Discrete Algorithms and Complexity10.1016/B978-0-12-386870-1.50023-X(311-324)Online publication date: 1987

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media