Page 1

Displaying 1 – 2 of 2

Showing per page

Polynomial time bounded truth-table reducibilities to padded sets

Vladimír Glasnák (2000)

Commentationes Mathematicae Universitatis Carolinae

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 of a...

Currently displaying 1 – 2 of 2

Page 1