# Tag Info

If one-way functions exist, then there is a distribution over graphs (or SAT formulas, or ...) having the property you're asking for. In short, just put the OWF through the Cook-Levin reduction. In a little more detail, Cook-Levin transforms the NP witness-finding question "what is a preimage of $y = f(x)$?" (for random unknown $x$) into the NP ...