1
$\begingroup$

I have been unable to find any literature on average-case complexity for coNP, other than a folklore conjecture that most tautologies are hard for any given propositional proof systems and some analysis of random k-SAT refutation. Am I missing something?

Is the following not a simple characterization: no paddable coNP-complete language is easy on average (in AvgP) if one such language has a stronger property invariant under p-isomorphism: for any Turing machine M accepting the language, P-uniform input families requiring superpolynomial time exist and appear with positive upper density in an enumeration of input families.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Every problem that can be solved in polynomial time is both in NP and coNP, so many problems in coNP can be solved in polynomial time.

Even if you look at coNP-complete, I can easily design a problem where the number of hard instances grows so slowly that the average time to solve an instance is polynomial or even linear.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Yes, my focus is on coNP-complete languages (eg tautologies, or "arithmetic sentences with no proof of size<=t", coBHP)--so could you spell out the design of a problem with such slow growth in the number of hard instances? It is hard to see how such a problem could have a 1-1 polynomial time reduction from the complement of bounded halting (coBHP={<N,x,1^t| nondeterministic N does not halt on x within t steps}) to your problem--to reduce hard instances of coBHP to the problem you design, the reduction would need to refer to superpolynomially larger instances of your problem. $\endgroup$
    – User315150
    Commented May 11, 2022 at 16:07
  • $\begingroup$ I haven't tried it, but start with the travelling salesman problem, change it to coNP-complete (change "is there a tour shorter than x" to "is there no tour shorter than x"). Then take all the numbers involved, write them as binary numbers, 0 or 1. Then you say "if any of the numbers is a decimal number with digits other than 0 or 1, then the answer is "NO"". Now you have say 2^100 problems with 100 bits worth of numbers, but almost 10^100 trivial instances. I think the average solution time might be quite short, because the "real" problems are totally outnumbered. $\endgroup$
    – gnasher729
    Commented May 11, 2022 at 16:22
  • $\begingroup$ This is an interesting idea. However, my question concerned TMs that accept not decide, so the NO instances are irrelevant, if I understand your approach. We would need a predominance of easy YES instances--I am not seeing how to achieve that. $\endgroup$
    – User315150
    Commented May 11, 2022 at 17:13
  • $\begingroup$ We decide what the problem is. Take my example, with a small change. "If any of the numbers is a decimal number with digits other than 0 or 1, then the answer is "YES". Now you have gazillions of instances with a trivial "Yes" answer. $\endgroup$
    – gnasher729
    Commented May 11, 2022 at 21:58
  • $\begingroup$ OK, so the counterexample is: take TSP, provide exactly 100 bit weights for each edge (even for 0 or 1 lengths), and for an n vertex graph, ask whether there is a circuit of length n, i.e, weight at most one for each edge (a Hamilton circuit). Then coTSP is easy on average as n grows larger, because a vanishing share 2^-99^n is hard (if even one edge has weight >1, the the graph is in coTSP). $\endgroup$
    – User315150
    Commented May 13, 2022 at 14:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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