Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-31T18:54:29.130Z Has data issue: false hasContentIssue false

On the Bit-Comprehension Rule

Published online by Cambridge University Press:  31 March 2017

By
Jan Johannsen  and
Chris Pollett
Edited by
Samuel R. Buss ,
Petr Hájek  and
Pavel Pudlák
Jan Johannsen
Affiliation:
Dept. of Mathematics U.C. San Diego
Chris Pollett
Affiliation:
Clark University Worcester, MA, USA
Samuel R. Buss
Affiliation:
University of California, San Diego
Petr Hájek
Affiliation:
Academy of Sciences of the Czech Republic, Prague
Pavel Pudlák
Affiliation:
Academy of Sciences of the Czech Republic, Prague
Get access
Type
Chapter
Information
Logic Colloquium '98 , pp. 262 - 279
Publisher: Cambridge University Press
Print publication year: 2000

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

B., Allen. Arithmetizing uniform NC. Annals of Pure and Applied Logic, 53:1–50, 1991.Google Scholar
E., Allender. The permanent requires large uniform threshold circuits. To appear in Chicago Journal of Theoretical Computer Science. Preliminary Version appeared in COCOON'96, 1998.
D.A.M., Barrington, N., Immermann, and H., Straubing. On uniformity within NC1. Journal of Computer and System Sciences, 41:274–306, 1990.Google Scholar
S.R., Buss. Bounded Arithmetic. Bibliopolis, Napoli, 1986.
P., Clote. A first order theory for the parallel complexity class NC. Technical Report BCCS-89-01, Boston College, January 1989.
P., Clote. On polynomial size Frege proofs of certain combinatorial principles. In P., Clote and J., Krajíček, editors, Arithmetic, Proof Theory and Computational Complexity, volume 23 of Oxford Logic Guides, pages 162–184. Clarendon Press, Oxford, 1993.
P., Clote and G., Takeuti. First order bounded arithmetic and small boolean circuit complexity classes. In P., Clote and J., Remmel, editors, Feasible Mathematics II, pages 154–218. Birkhäuser, Boston, 1995.
J., Johannsen. A bounded arithmetic theory for constant depth threshold circuits. In P., Hájek, editor, GÖDEL '96, pages 224–234, 1996. Springer Lecture Notes in Logic 6.
J., Johannsen and C., Pollett. On proofs about threshold circuits and counting hierarchies (extended abstract). In Proc. 13th IEEE Symposium on Logic in Computer Science, pages 444–452, 1998.
J., Krajíček. Bounded Arithmetic, Propositional Logic and Complexity Theory. Cambridge University Press, 1995.
J., Krajíček, P., Pudlák, and J., Sgall. Interactive computations of optimal solutions. In B., Rovan, editor, Mathematical Foundations of Computer Science, pages 48–60. Springer, 1990.
J., Krajíček, P., Pudlák, and G., Takeuti. Bounded arithmetic and the polynomial hierarchy. Annals of Pure and Applied Logic, 52:143–153, 1991.Google Scholar
P., Pudlák. Some relations between subsystems of arithmetic and complexity of computations. In Y.N., Moschovakis, editor, Logic fromComputer Science, pages 499–519. Springer, New York, 1992.
G., Takeuti. RSUV isomorphisms. In P., Clote and J., Krajíček, editors, Arithmetic, Proof Theory and Computational Complexity, volume 23 of Oxford LogicGuides, pages 364–386. Clarendon Press, Oxford, 1993.

Save book to Kindle

To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

Available formats
×