It is well known that if OWFs/PRGs exist, then there is a zero knowledge proof for any NP-complete language, say G3C (graph coloring in 3 colors). The zero-knowledge notion maintains that any malicious verifier that interacts with the prover can be simulated by a PPT algorithm (including the communication) and thus, doesn't gain any advantage from the prover's replies.
Yet, if a PPT algorithm can find a coloring in a graph with non-negligible probability (even without interacting with a prover), then the whole notion of zero-knowledge proofs for NP-Complete languages becomes useless!
Is there a distribution over graphs that enables generating graphs for which no PPT algorithm can find a 3-coloring in non-negligible probability?? (under the assumptions of P!=NP and OWF & PRGs exist). Or a distribution over graphs that enables generating graphs for which no PPT algorithm can determine if they are in G3C or not with non-negligible advantage? Otherwise I can't see how such a ZK proof can be beneficial.