Displaying similar documents to “Self-reducibility structures and solutions of NP problems.”

Function operators spanning the arithmetical and the polynomial hierarchy

Armin Hemmerling (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

A modified version of the classical -operator as well as the first value operator and the operator of inverting unary functions, applied in combination with the composition of functions and starting from the primitive recursive functions, generate all arithmetically representable functions. Moreover, the nesting levels of these operators are closely related to the stratification of the arithmetical hierarchy. The same is shown for some further function operators known from computability...

Polynomial time bounded truth-table reducibilities to padded sets

Vladimír Glasnák (2000)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

We study bounded truth-table reducibilities to sets of small information content called padded (a set is in the class f -PAD of all f -padded sets, if it is a subset of { x 10 f ( | x | ) - | x | - 1 ; x ∈ { 0 , 1 } * } ). This is a continuation of the research of reducibilities to sparse and tally sets that were studied in many previous papers (for a good survey see [HOW1]). We show necessary and sufficient conditions to collapse and separate classes of bounded truth-table reducibilities to padded sets. We prove that depending on two properties...