2026-07-25T06:57:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15661 2024-03-06T10:55:53Z ddc:004 open_access

Pseudorandom Self-Reductions for NP-Complete Problems Elrazik, Reyad Abed Robere, Robert Schuster, Assaf Yehuda, Gal computational complexity pseudorandomness worst-case to average-case self reductions planted clique hereditary graph family A language L is random-self-reducible if deciding membership in L can be reduced (in polynomial time) to deciding membership in L for uniformly random instances. It is known that several "number theoretic" languages (such as computing the permanent of a matrix) admit random self-reductions. Feigenbaum and Fortnow showed that NP-complete languages are not non-adaptively random-self-reducible unless the polynomial-time hierarchy collapses, giving suggestive evidence that NP may not admit random self-reductions. Hirahara and Santhanam introduced a weakening of random self-reductions that they called pseudorandom self-reductions, in which a language L is reduced to a distribution that is computationally indistinguishable from the uniform distribution. They then showed that the Minimum Circuit Size Problem (MCSP) admits a non-adaptive pseudorandom self-reduction, and suggested that this gave further evidence that distinguished MCSP from standard NP-Complete problems. We show that, in fact, the Clique problem admits a non-adaptive pseudorandom self-reduction, assuming the planted clique conjecture. More generally we show the following. Call a property of graphs π hereditary if G ∈ π implies H ∈ π for every induced subgraph of G. We show that for any infinite hereditary property π, the problem of finding a maximum induced subgraph H ∈ π of a given graph G admits a non-adaptive pseudorandom self-reduction. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Reyad Abed Elrazik and Robert Robere and Assaf Schuster and Gal Yehuda 2022 Is Part Of LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2022.65 urn:nbn:de:0030-drops-156615 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.65 eng https://creativecommons.org/licenses/by/4.0/legalcode