3
$\begingroup$

$1)$Can a $NP$-hard problem can have short certificates that can be verified in deterministic polynomial time for ALL but $\frac{1}{n}$ of the NO instances$?

$2)$ Can one concoct versions of NP complete problems $\Pi_1$ and $\Pi_2$ where probability $p=P(\Pi_2=NO|\Pi_1=YES)=P(\Pi_1=NO|\Pi_2=YES)$ is between $\frac{1}{2}+\epsilon$ and $1-\epsilon$? Then almost all the time short certificates are possible as in $1)$ if $p$ is closer to $1-\epsilon$.

$\endgroup$
9
  • $\begingroup$ So when you talk about probabilities in the question, what distribution do you mean? Uniform over instances of a fixed size? Note that what that means might also depend on encoding. $\endgroup$ Dec 1 '13 at 17:31
  • 1
    $\begingroup$ I removed my obsolete comments, you could do the same. You need to define formally what "have short certificates" means. It seems you allow a verifier to make a mistake, while I think a more standard definition is that the verifier is always correct, but may not always run in polynomial time. For another thing, your definition in 1) says there should be a certificate for most of the NO instances, so the probability of a no instances should make no difference, and your remark in 3) makes no sense. $\endgroup$ Dec 2 '13 at 18:24
  • 1
    $\begingroup$ May be I am misunderstanding, that is why I wrote you should make your question more precise. E.g. let's make it more concrete: are you asking that TAUT has a polytime verifier with short proofs for all but a 1/n factions of propositional tautologies of size n? $\endgroup$
    – Kaveh
    Dec 3 '13 at 16:06
  • 1
    $\begingroup$ Generally, AFAIU, heuristic algorithms are those that can fail completely on a small fraction of inputs (w.r.t. to some given ensemble). Maybe you want to know something like $(U,TAUT) \in? HeurNP$ where $U$ is the uniform ensemble (i.e. all inputs of the same size are equally likely)? $\endgroup$
    – Kaveh
    Dec 3 '13 at 16:09
  • 1
    $\begingroup$ aha! Now your comments make sense to me. "are you asking that TAUT has a polytime verifier with short proofs for all but a 1/n factions of propositional tautologies of size n?" Exactly is there any thing that would break down in complexity from getting such a result? "(U,TAUT)∈?HeurNP where U is the uniform ensemble" This is another way to look at my second problem perhaps. Is there anything in theory that will break down if we have something like this and hence impossible from a common sense wisdom view? $\endgroup$
    – Mr.
    Dec 3 '13 at 16:18
2
$\begingroup$

You can construct artificial examples by padding. For example, take an NP-hard language $L$ and pad it by zeroes to $L'=\{x0^{|x|^2}|x\in L\}$. Then the original instances form only a $2^{-n^2}$ fraction, and the answer to the fraction $1-2^{-n^2}$ of the instances is trivially "no" (no certificate is needed at all), yet the language remains NP-hard.

If you look specifically at SAT and the uniform distribution, you need to specify a particular encoding of formulas into bit strings (it will change the effective distribution on formulas). See, for example, the paper by Frieze, Goerdt, and Krivelevich on easy random SAT instances and short proofs of unsatisfiability.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.