Menu
Home
Contact us
Stats
Categories
Calendar
Toggle Wiki
Wiki Home
Last Changes
Rankings
List pages
Orphan pages
Sandbox
Print
Toggle Image Galleries
Galleries
Rankings
Toggle Articles
Articles home
List articles
Rankings
Toggle Blogs
List blogs
Rankings
Toggle Forums
List forums
Rankings
Toggle File Galleries
List galleries
Rankings
Toggle Maps
Mapfiles
Toggle Surveys
List surveys
Stats
ITHEA Classification Structure > F. Theory of Computation  > F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES  > F.4.1 Mathematical Logic 
COMPARISON OF PROOF SIZES IN FREGE SYSTEMS AND SUBSTITUTION FREGE SYSTEMS
By: Anahit Chubaryan, Hakob Nalbandyan (2167 reads)
Rating: (1.00/10)

Abstract: It is known that the minimal number of the steps in a proof of a tautology in a Frege system can be exponentially larger than in a substitution Frege system, but it is an open problem whether Frege systems can polynomially simulate substitution Frege systems by sizes. Many people conjecture that the answer is no. We prove that the answer is yes. As a bridge between substitution Frege systems and Frege systems we consider the Frege systems, augmented with restricted substitution (single renaming) rule. We prove that Frege systems with single renaming rule polynomially simulate by size Frege systems with substitution rule without any restrictions, and Frege systems without substitution rule polynomially simulate Frege systems with single renaming rule both by steps and by size.

Keywords: Frege system, proof complexity, depth-restricted substitution rule, k-bounded substitution rule, polynomial simulation, exponential speed-up.

ACM Classification Keywords: F.4.1 Mathematical Logic and Formal Languages, Mathematical Logic, Proof theory

Link:

COMPARISON OF PROOF SIZES IN FREGE SYSTEMS AND SUBSTITUTION FREGE SYSTEMS

Anahit Chubaryan, Hakob Nalbandyan

http://www.foibg.com/ijita/vol17/ijita17-2-p04.pdf

Print
F.4.1 Mathematical Logic
article: UNIVERSAL AND DETERMINED CONSTRUCTORS OF MULTISETS OF OBJECTS · PROOF COMPLEXITIES OF SOME PROPOSITIONAL FORMULAE CLASSES IN DIFFERENT ... · COMPARISON OF PROOF SIZES IN FREGE SYSTEMS AND SUBSTITUTION FREGE SYSTEMS · ALGORITHMIZATION PROCESS FOR FRACTAL ANALYSIS IN THE CHAOTIC DYNAMICS OF ... · ON PROBLEM OF ADEQUACY OF MULTISET MATHEMATICAL MODELS · PROOF COMPLEXITIES OF SOME PROPOSITIONAL FORMULAE CLASSES IN DIFFERENT ... · ACCOUNTING IN THEORETICAL GENETICS · СЕМАНТИЧЕСКИЕ СВОЙСТВА И СЕКВЕНЦИАЛЬНЫЕ ИС · МОДАЛЬНЫЕ ЛОГИКИ ЧАСТИЧНЫХ ПРЕДИКАТОВ И СЕ� · CONTRADICTION VERSUS SELFCONTRADICTION IN FUZZY LOGIC* · A GEOMETRICAL INTERPRETATION TO DEFINE CONTRADICTION ·
Login
[ register | I forgot my password ]
World Clock
Powered by Tikiwiki Powered by PHP Powered by Smarty Powered by ADOdb Made with CSS Powered by RDF powered by The PHP Layers Menu System
RSS Wiki RSS Blogs rss Articles RSS Image Galleries RSS File Galleries RSS Forums RSS Maps rss Calendars
[ Execution time: 0.09 secs ]   [ Memory usage: 7.52MB ]   [ GZIP Disabled ]   [ Server load: 0.31 ]
Powered by Tikiwiki CMS/Groupware