<p>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.</p>

<p>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, <a href="http://www.math.tau.ac.il/~krivelev/SAT.ps" rel="nofollow" title="Frieze, Goerdt, Krivelevich">the paper by Frieze, Goerdt, and Krivelevich</a> on easy random SAT instances and short proofs of unsatisfiability.</p>

CC BY-SA 3.0
2013-12-15T12:26:54.283Z
2013-12-15T13:15:05.080Z
2013-12-15T13:15:05.080Z
hirsch
<p>$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$?</p>

<p>$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$.</p>

CC BY-SA 3.0
2013-12-01T17:31:17.653Z
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.
Sasho Nikolov
CC BY-SA 3.0
2013-12-01T17:34:22.040Z
Take subset sum for instance where the sizes of integers are such that, it makes the problem $NPC$, then you pick the integers without replacement assuming uniform distribution. I think this is a reasonable scenario.
Turbo
CC BY-SA 3.0
2013-12-02T18:24:55.520Z
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.
Sasho Nikolov
CC BY-SA 3.0
2013-12-03T13:19:53.300Z
1. You have to clarify what probabilities you are talking about (i.e. probability over what space?). I think you should restate the question in terms of distributional problems. 2. It seems you are looking for something like [HeurP](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:H#heurp) and its nondeterministic counterpart, and if I understand correctly, you are asking something like: "_is [DistNP](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:D#distnp) contained in [HeurP](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:H#heurp)?_" which is probably an open problem.
Kaveh
CC BY-SA 3.0
2013-12-03T14:21:43.987Z
@Kaveh I checked the definitions of DistNP and HP(as in Impagliazzo's paper). It looks like DistNP is not HP is some kind of version of NP is not P. So the answer to 2 in your comment is No _ I am not looking for this. I am assuming generating certificates for YES instances may be hard and that $NP\neq P$ is true. What I am trying to say is "is there a possibility that NO instances of NPC problems can have short certificates(which may be hard to find) for all but a negligible portion of NO instance inputs to the problem?" Is there any impossibility results for this? Is such a result possible?
Turbo
CC BY-SA 3.0
2013-12-03T14:43:09.493Z
@Kaveh I am unfamiliar with HeurP and DistNP then. Could you clarify your thoughts why the current situation seems that way? Let me try to relate to my thoughts.
Turbo
CC BY-SA 3.0
2013-12-03T16:06:29.430Z
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?
Kaveh
CC BY-SA 3.0
2013-12-03T16:09:59.553Z
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)?
Kaveh
CC BY-SA 3.0
2013-12-03T16:18:55.120Z
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?
Turbo
<cc.complexity-theory><complexity-classes>
On $NP=coNP$ problem in average case
Turbo
# On $NP=coNP$ problem in average case

(Asked by: username_0 on 2013-12-01)

$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$.

**Tags:** cc.complexity-theory, complexity-classes

> **Comments:**
> **username_1**: 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.  
> **username_0**: Take subset sum for instance where the sizes of integers are such that, it makes the problem $NPC$, then you pick the integers without replacement assuming uniform distribution. I think this is a reasonable scenario.  
> **username_1**: 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.  
> **username_2**: 1. You have to clarify what probabilities you are talking about (i.e. probability over what space?). I think you should restate the question in terms of distributional problems. 2. It seems you are looking for something like [HeurP](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:H#heurp) and its nondeterministic counterpart, and if I understand correctly, you are asking something like: "_is [DistNP](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:D#distnp) contained in [HeurP](https://complexityzoo.uwaterloo.ca/Complexity_Zoo:H#heurp)?_" which is probably an open problem.  
> **username_0**: @username_2 I checked the definitions of DistNP and HP(as in Impagliazzo's paper). It looks like DistNP is not HP is some kind of version of NP is not P. So the answer to 2 in your comment is No _ I am not looking for this. I am assuming generating certificates for YES instances may be hard and that $NP\neq P$ is true. What I am trying to say is "is there a possibility that NO instances of NPC problems can have short certificates(which may be hard to find) for all but a negligible portion of NO instance inputs to the problem?" Is there any impossibility results for this? Is such a result possible?  
> **username_0**: @username_2 I am unfamiliar with HeurP and DistNP then. Could you clarify your thoughts why the current situation seems that way? Let me try to relate to my thoughts.  
> **username_2**: 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?  
> **username_2**: 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)?  
> **username_0**: 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?  

---

## 1 answers

### Answer by username_3 on 2013-12-15. Score: 2 | Accepted answer

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](http://www.math.tau.ac.il/~krivelev/SAT.ps "Frieze, Goerdt, Krivelevich") on easy random SAT instances and short proofs of unsatisfiability.


---

