A proof complexity generator

Number of the records: 1

1.

SYSNO ASEP	0353760
Document Type	C - Proceedings Paper (int. conf.)
R&D Document Type	Conference Paper
Title	A proof complexity generator
Author(s)	Krajíček, Jan (MU-W)_{SAI, ORCID}
Source Title	Logic, Methodology and Philosophy of Science. - London : College Publications, 2009 / Glymour C. ; Wang W. ; Westerstahl D. - ISBN 978-1-904987-45-1
Pages	s. 185-190
Number of pages	6 s.
Action	International Congress in Logic, Methodology and Philosophy of Science /13./
Event date	09.08.2007-15.08.2007
VEvent location	Beijing
Country	CN - China
Event type	WRD
Language	eng - English
Country	GB - United Kingdom
Keywords	proof complexity ; hard tatologies
Subject RIV	BA - General Mathematics
R&D Projects	IAA1019401 GA AV ČR - Academy of Sciences of the Czech Republic (AV ČR)
	LC505 GA MŠMT - Ministry of Education, Youth and Sports (MEYS)
Annotation	We define by a 2DNF formula a Boolean map from n bits to n+1 bits such that in any propositional proof system for which the PHP principle is hard, it is hard to prove about any n+1 string that it is outside of the range of the map.
Workplace	Mathematical Institute
Contact	Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757
Year of Publishing	2011

Number of the records: 1