We will prove the exponential PCP theorem in the theory APC_1, the PCP theorem in PV_1, assuming certain facts about (n,d,lambda)-graphs, and will discuss the possibility of deriving the PCP theorem in S^1_2 unconditionally.

Chair: Pavel Pudlak, Neil Thapen, Jan Krajíček

More information on the old seminar web page. The programme is announced via the mailing list.

Charles University

Monday, 28. April 2014 - 13:30

We will prove the exponential PCP theorem in the theory APC_1, the PCP theorem in PV_1, assuming certain facts about (n,d,lambda)-graphs, and will discuss the possibility of deriving the PCP theorem in S^1_2 unconditionally.

Institute of Mathematics, AS CR

Monday, 7. April 2014 - 13:30

Wiles's proof of Fermat's Last Theorem (FLT) has stimulated a lively
discussion on how much is actually needed for the proof. Despite the fact
that the original proof uses set-theoretical assumptions unprovable in
Zermelo-Fraenkel set theory with axiom of choice (ZFC), it is widely believed
that much less is needed in principle. Harvey Friedman even conjectured that
Fermat's Last Theorem is provable in so called elementary function arithmetic
(EFA) (which is just ISigma_0 + "2^x is total" in a different language).
Smith has showed that EFA proves Fermat's Last Theorem for some small even
exponents n (e.g. for n = 4, 6, 10). On the other hand Shepherdson and
recently Kolodziejczyk constructed models of IOpen and T^0_2 respectively,
where FLT does not hold for n=3.
I will present a joint work with Vítězslav Kala. We consider structures and
theories in the language L^e=(0,1,+,*,e,

Charles University

Monday, 10. March 2014 - 13:30

We will prove the exponential PCP theorem in the theory $APC_1$, the PCP theorem in $PV_1$, assuming certain facts about $(n,d,lambda)$-graphs, and will discuss the possibility of deriving the PCP theorem in $S^1_2$ unconditionally.