Reducibility by means of almost polynomial functions

DOI10.3103/S1066369X2212009XMaRDI QIDQ6132642zbMATH OpenOpenAlexFDO

Authors S. S. Marchenkov

Publication date 14 July 2023

Published in Russian Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3103/s1066369x2212009x

zbMATH Keywords

\(m\)-reducibilityalmost polynomial functions

Mathematics Subject Classification ID

Other degrees and reducibilities in computability and recursion theory (03D30)

Recommendations

• scientific article; zbMATH DE number 3902637
• Strong polynomial-time reducibility
• \(m\)-reducibility with upper and lower bounds for reducing functions
• On bounded \(m\)-reducibilities
• Polynomial-time reducibilities and ``almost all oracle sets

Cites work

• scientific article; zbMATH DE number 5533356 (Why is no real title available?)
• scientific article; zbMATH DE number 4104394 (Why is no real title available?)
• scientific article; zbMATH DE number 8116 (Why is no real title available?)
• scientific article; zbMATH DE number 3634246 (Why is no real title available?)
• scientific article; zbMATH DE number 1232433 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• Boolean reducibility
• Closed left-r.e. sets
• Complete and incomplete Boolean degrees
• Complete degrees of finite-state transformability
• On maximal and minimal elements of partially ordered sets of Boolean degrees
• On the structure of partially ordered sets of Boolean degrees
• Reducibility among combinatorial problems
• Statistical estimation of the structure of a finite population
• Strong reducibilities
• The complexity of theorem-proving procedures

Cited in

(10)

• A solution for reducing the degree of polynomial composition functions using Faà di Bruno's formula and Fourier transform
• Associative idempotent nondecreasing functions are reducible
• Poly-element equations reducible to moment problem for entire functions of class A
• scientific article; zbMATH DE number 5144071 (Why is no real title available?)
• The total reducibility order of a polynomial in two variables
• A note on polynomial reduction
• A poly-algorithmic approach to simplifying elementary functions
• On the reduced length of a polynomial with real coefficients
• Reducibility of polynomials of the form f(x)-g(y)
• \(m\)-reducibility with upper and lower bounds for reducing functions

This page was built for publication: Reducibility by means of almost polynomial functions

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