- New
-
Topics
- All Categories
- Metaphysics and Epistemology
- Value Theory
- Science, Logic, and Mathematics
- Science, Logic, and Mathematics
- Logic and Philosophy of Logic
- Philosophy of Biology
- Philosophy of Cognitive Science
- Philosophy of Computing and Information
- Philosophy of Mathematics
- Philosophy of Physical Science
- Philosophy of Social Science
- Philosophy of Probability
- General Philosophy of Science
- Philosophy of Science, Misc
- History of Western Philosophy
- Philosophical Traditions
- Philosophy, Misc
- Other Academic Areas
- Journals
- Submit material
- More
Nisan-Wigderson generators in proof systems with forms of interpolation
Mathematical Logic Quarterly 57 (4):379-383 (2011)
Abstract
We prove that the Nisan-Wigderson generators based on computationally hard functions and suitable matrices are hard for propositional proof systems that admit feasible interpolation. © 2011 WILEY-VCH Verlag GmbH & Co. KGaA, WeinheimLinks
PhilArchive
External links
(no proxy)
Setup an account with your affiliations in order to access resources via your University's proxy server
Through your library
- Sign in / register and customize your OpenURL resolver
- Configure custom resolver
My notes
Similar books and articles
On the proof complexity of the nisan–wigderson generator based on a hard np ∩ conp function.Jan Krajíček - 2011 - Journal of Mathematical Logic 11 (1):11-27.
Interpolation theorems, lower Bounds for proof systems, and independence results for bounded arithmetic.Jan Krajíček - 1997 - Journal of Symbolic Logic 62 (2):457-486.
Interpolation and Approximate Semantic Derivations.Jan Krajíček - 2002 - Mathematical Logic Quarterly 48 (4):602-606.
An exponential lower bound for a constraint propagation proof system based on ordered binary decision diagrams.Jan Krajíček - 2008 - Journal of Symbolic Logic 73 (1):227-237.
Interpolation in fragments of classical linear logic.Dirk Roorda - 1994 - Journal of Symbolic Logic 59 (2):419-444.
A constructive proof of Craig's interpolation lemma for m-valued logic.Anita Waselewska - 1979 - Studia Logica 38 (3):267 - 275.
Consequence and Interpolation in Łukasiewicz Logic.Daniele Mundici - 2011 - Studia Logica 99 (1-3):269-278.
Discretely ordered modules as a first-order extension of the cutting planes proof system.Jan Krajíček - 1998 - Journal of Symbolic Logic 63 (4):1582-1596.
Do there exist complete sets for promise classes?Olaf Beyersdorff & Zenon Sadowski - 2011 - Mathematical Logic Quarterly 57 (6):535-550.
Realisability in weak systems of explicit mathematics.Daria Spescha & Thomas Strahm - 2011 - Mathematical Logic Quarterly 57 (6):551-565.
Analytics
Added to PP
2013-12-01
Downloads
15 (#923,100)
6 months
5 (#629,136)
2013-12-01
Downloads
15 (#923,100)
6 months
5 (#629,136)
Historical graph of downloads
Citations of this work
On the proof complexity of the nisan–wigderson generator based on a hard np ∩ conp function.Jan Krajíček - 2011 - Journal of Mathematical Logic 11 (1):11-27.
References found in this work
Interpolation theorems, lower Bounds for proof systems, and independence results for bounded arithmetic.Jan Krajíček - 1997 - Journal of Symbolic Logic 62 (2):457-486.
Lower Bounds for resolution and cutting plane proofs and monotone computations.Pavel Pudlák - 1997 - Journal of Symbolic Logic 62 (3):981-998.
Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic.Jan Krajíček - 1997 - Journal of Symbolic Logic 62 (2):457-486.
PhilPapers logo by Andrea Andrews and Meghan Driscoll.
This site uses cookies and Google Analytics (see our terms & conditions for details regarding the privacy implications). Use of this site is subject to terms & conditions.
All rights reserved by The PhilPapers Foundation
Server: philpapers-web-7c76586df8-hc2g5 uwo