MONOTONOUS AND RANDOMIZED REDUCTIONS TO SPARSE SETS

摘要

An oracle machine is called monotonous, if after a negative answer the machine does not ask further queries to the oracle. For example, one-query truth-table, conjunctive, and Hausdorff reducibilities are monotonous. We study the consequences of the existence of sparse hard sets for different complexity classes under monotonous and randomized reductions. We prove trade-offs between the randomized time complexity of NP sets that reduce to a set B via such reductions and the density of B as well as the number of queries made by the monotonous reduction. As a consequence, bounded Turing hard sets for NP are not co-rp reducible to a sparse set unless RP = NP. We also prove similar results under the apparently weaker assumption that some solution of the promise problem (1SAT, SAT) reduces via the mentioned reductions to a sparse set.%Une machine d'oracle est appelée monotone si elle ne pose pas d'autre question à l'oracle après une réponse négative. Par exemple, les réductibilités 1-tt, conjonctive ou de Hausdorff sont monotones. Nous étudions les conséquences de l'existence d'ensembles dures et sparse pour différentes classes de complexité sous des réductions monotones et randomisées. Nous prouvons des trade-off entre la complexité randomisée du temps d'ensembles NP qui réduisent à un ensemble B via de telles réductions et la densité de B, aussi bien que le nombre des questions posées par les réductions monotones. Par conséquence, des ensembles durs pour NP par rapport à la réductibilité bornée de Turing ne sont pas réductibles co-rp à un ensemble sparse sauf si RP = NP. Nous prouvons également des résultats similaires sous l'hypothèse apparemment plus faible qu'une solution du promise problem (1SAT, SAT) réduit via les réductions mentionnées à un ensemble sparse.