scientific article; zbMATH DE number 3936520

From MaRDI portal
Publication:3707409





[For the entire collection see Zbl 0553.00001.] Our purpose here is to give a brief discussion of a very strict notion of reducibility called p-projection. Further details can be found e.g. in the author's papers in Proc. 11th ACM Symp. Theory of Computing, 249-261 (1979) and in Logic and algorithmic. Monogr. L'Enseign. Math. 30, 365-380 (1982; Zbl 0474.68062). The remarkable property of this notion of reduction is that in spite of its demanding and restricted nature numerous natural problems that superficially look dissimilar can be related by it. It is applicable to a variety of algebraic structures among which rings of multivariate polynomials and Boolean algebras are important examples. It can be used to give an account to the relative difficulty of computational problems almost without having to define models of computation.




Cited in
(28)








This page was built for publication:

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