Premium
Nisan‐Wigderson generators in proof systems with forms of interpolation
Author(s) -
Pich Ján
Publication year - 2011
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.201010012
Subject(s) - interpolation (computer graphics) , mathematics , proof of concept , discrete mathematics , computer science , operating system , telecommunications , frame (networking)
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, Weinheim
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom