_ 0-complexity of the relation y= _i n F(i)

DOI10.1016/0168-0072(94)00055-8zbMATH Open0838.03042OpenAlexW2008286614MaRDI QIDQ1899142FDOQ1899142

Authors: Alessandro Berarducci, Paola D'Aquino 

Publication date: 5 November 1995

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0168-0072(94)00055-8

Recommendations

• scientific article
• On a complexity of the formula \((A\bigvee B) \Rightarrow C\)
• Measures related to \((\varepsilon,n)\)-complexity functions
• Complexity of finite-variable fragments of products with K
• Complexity classes between $\Theta _k^P$ and $\Delta _k^P$
• CONVERGENCE OF C₀ COMPLEXITY
• On the quantifier complexity of \(\Delta_{n+1}(T)\)-induction
• scientific article; zbMATH DE number 1855658
• Abstract complexity theory and the \(\Delta_{2}^{0}\) degrees
• Towards the computational complexity of \(\mathcal{PR}^ \omega\)-terms

zbMATH Keywords

fragment of Peano arithmetic\(\Delta_ 0\)-definable functioninduction restricted to bounded formulas

Mathematics Subject Classification ID

First-order arithmetic and fragments (03F30)

Cites Work

• On the scheme of induction for bounded arithmetic formulas
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Rudimentary Predicates and Relative Computation
• Local behaviour of the Chebyshev theorem in models of I⊿₀
• Provability of the pigeonhole principle and the existence of infinitely many primes
• Expectations for Inbreeding Depression on Self-Fertilization of Tetraploids
• Title not available (Why is that?)
• Counting $Δ_0$ sets

Cited In (5)

• Commutative unital rings elementarily equivalent to prescribed product rings
• Passive induction and a solution to a Paris-Wilkie open question
• Iterated multiplication in \(VTC^0\)
• Non-standard finite fields over \(I\Delta_0+\Omega_1\)
• Title not available (Why is that?)

This page was built for publication: \(\Delta_ 0\)-complexity of the relation \(y= \prod_{i\leq n} F(i)\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1899142)