Pseudorandom generators, measure theory, and natural proofs [PDF]
Proceedings of IEEE 36th Annual Foundations of Computer Science, 2002 We prove that if strong pseudorandom number generators exist, then the class of languages that have polynomial-sized circuits (P/poly) is not measurable within exponential time, in terms of the resource-bounded measure theory of Lutz. We prove our result by showing that if P/poly has measure zero in exponential time, then there is a natural proof ...
K.W. Regan +2 more
openaire +1 more source
Proof Theory of Finite-valued Logics [PDF]
, 1993 The proof theory of many-valued systems has not been investigated to an extent comparable to the work done on axiomatizatbility of many-valued logics. Proof theory requires appropriate formalisms, such as sequent calculus, natural deduction, and tableaux
Zach, Richard
core +5 more sources
Towards a group theoretical proof of the Frobenius theorem [PDF]
Journal of Mahani Mathematical ResearchThe Frobenius finite group was defined by Frobenius more than 100 years ago to be a group with a non-trivial proper subgroup $H$ whose intersection with all of its conjugates is the trivial group.
Mohammad Reza Darafsheh
doaj +1 more source
Relativistic Electromagnetic Mass Models: Charged Dust Distribution in Higher Dimensions [PDF]
, 2005 Electromagnetic mass models are proved to exist in higher dimensional theory of general relativity corresponding to charged dust distribution. Along with the general proof a specific example is also sited as a supporting candidate.Comment: Latex, 7 pages.
A. Banerjee +22 more
core +2 more sources
PROOFTOOL: a GUI for the GAPT Framework [PDF]
Electronic Proceedings in Theoretical Computer Science, 2013 This paper introduces PROOFTOOL, the graphical user interface for the General Architecture for Proof Theory (GAPT) framework. Its features are described with a focus not only on the visualization but also on the analysis and transformation of proofs and ...
Cvetan Dunchev +6 more
doaj +1 more source
Unique perfect matchings, forbidden transitions and proof nets for linear logic with Mix [PDF]
Logical Methods in Computer Science, 2020 This paper establishes a bridge between linear logic and mainstream graph theory, building on previous work by Retor\'e (2003). We show that the problem of correctness for MLL+Mix proof nets is equivalent to the problem of uniqueness of a perfect ...
Lê Thành Dũng Nguyên
doaj +1 more source
Constructive pointfree topology eliminates non-constructive representation theorems from Riesz space theory [PDF]
, 2008 In Riesz space theory it is good practice to avoid representation theorems which depend on the axiom of choice. Here we present a general methodology to do this using pointfree topology.
AC Zaanen +25 more
core +4 more sources
The Fundamental Problem of General Proof Theory [PDF]
Studia Logica, 2018 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
openaire +1 more source
The zeroth law of black hole thermodynamics in arbitrary higher derivative theories of gravity
Journal of High Energy Physics, 2022 We consider diffeomorphism invariant theories of gravity with arbitrary higher derivative terms in the Lagrangian as corrections to the leading two derivative theory of Einstein’s general relativity.
Sayantani Bhattacharyya +3 more
doaj +1 more source
Characterization of incentive compatible single-parameter mechanisms revisited
Journal of Mechanism and Institution Design, 2022 We reexamine the characterization of incentive compatible single-parameter mechanisms introduced in Archer and Tardos (2001). We argue that the claimed uniqueness result, called 'Myerson's Lemma' was not well established.
Krzysztof R. Apt, Jan Heering
doaj +1 more source