Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-28T05:13:27.350Z Has data issue: false hasContentIssue false
  • English
  • Français

Parallel strategies

Published online by Cambridge University Press:  12 March 2014

Pavel Pudlák
Pavel Pudlák*
Affiliation:
Mathematical Institute, AV ČR, and Institute for Theoretical Computer Science, Prague, Czech Republic, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider combinatorial principles based on playing several two person games simultaneously. We call strategies for playing two or more games simultaneously parallel. The principles are easy consequences of the determinacy of games, in particular they are true for all finite games. We shall show that the principles fail for infinite games. The statements of these principles are of lower logical complexity than the sentence expressing the determinacy of games, therefore, they can be studied in weak axiomatic systems for arithmetic (Bounded Arithmetic). We pose several open problems about the provability of these statements in Bounded Arithmetic and related computational problems.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 68 , Issue 4 , December 2003 , pp. 1242 - 1250
Copyright
Copyright © Association for Symbolic Logic 2003

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1] Buss, S., Bounded arithmetic, Bibliopolis, 1986.Google Scholar
[2] Gale, D. and Steward, F., Infinite games with perfect information, Annals of Mathematics Studies, vol. 28 (1953), pp. 245–266.Google Scholar
[3] Hájek, P. and Pudlák, P., Metamathematics of First-Order Arithmetic, Springer, 1993.Google Scholar
[4] Krajíček, J., Bounded Arithmetic, Propositional Logic and Complexity Theory, Cambridge University Press, 1995.Google Scholar