# Non rigorous argument that $P \ne NP$ implies $avgP \ne distNP$

Consider the following nonrigorous argument that $$P \neq NP$$ implies $$avgP \neq distNP$$. (For those unfamiliar with the latter complexity classes, they deal with average case hardness.)

Suppose A is the algorithm that solves some NP complete problem (say 3-SAT) with the fastest average case complexity possible and suppose that this complexity is polynomial. Then given that $$P \neq NP$$, this algorithm must run in super-polynomial time on some subset of all inputs to 3-SAT.

Now let us define a new NP-complete problem (call it 3-SAT’) where its instances are all instances of 3-SAT in which algorithm A takes super-polynomial time to run.

Then no algorithm A’ that solves 3-SAT’ can run in polynomial time on average - if it could, then it would be possible to create a new algorithm that solves 3-SAT faster on average than algorithm A by applying algorithm A to all non instances of 3-SAT’ and applying algorithm A’ to all instances of 3-SAT’.

Therefore, $$P \neq NP$$ implies $$avgP \neq distNP$$.

One problem with this argument is that it assumes that it is possible to tell the difference in polynomial time between instances of 3-SAT’ and non instances of 3-SAT’; in other words the argument assumes it is possible to efficiently determine which instances of 3-SAT are hard, which I am not sure is true.

Has my observation been made in the literature and how has it been dealt with? Are there any other problems with my argument?

Let $$X$$ be the chosen subset of inputs to which we can restrict 3-SAT such that algorithm A remains superpolynomial.

Then no algorithm A’ that solves 3-SAT’ can run in polynomial time on average

This does not follow from your argument. At best, assuming you can determine whether input lies in $$X$$ in polynomial time, this argument shows any algorithm that solves 3-SAT' in polynomial time has the same running time as A on $$X$$. For example, if we choose $$X$$ to be equal to all inputs of 3-SAT, the algorithm A is a valid choice for A'.

In general, you would need to prove there is an algorithm that is strictly faster on average than algorithm A on $$X$$. While it would seem easier to construct an efficient algorithm for only $$X$$ and not the rest of the input, there is no guarantee that the restricted input gives a more efficient algorithm.

As for the literature, I believe it is unknown whether $$\mathsf{P}\neq \mathsf{NP}$$ implies $$\mathsf{avgP}\neq \mathsf{distNP}$$. What is known is that $$\mathsf{E}\neq \mathsf{NE}$$ implies $$\mathsf{avgP}\neq \mathsf{distNP}$$ (S. Ben-David, B. Chor, O. Goldreich, and M. Luby. On the theory of average case complexity, Journal of Computer and System Sciences 44(2):193-219, 1992.)

• But in my argument, A’ is assumed to be strictly faster on average on input X than algorithm A is on input X, since it is polynomial time on average on X, while A is super polynomial for all inputs in X. So I don’t understand your objection. Mar 16, 2023 at 16:04
• It may be possible for an algorithm to both be super-polynomial on X in the worst case and polynomial on average for X. For instance, under your assumptions, algorithm A has this when X is the entire input space. Maybe I do not understand what you mean by a super-polynomial subset, can you clarify? Mar 16, 2023 at 16:18
• I don’t think I said “super polynomial subset”. Super polynomial means something like exponential. It seems like you are misunderstanding my question. Mar 16, 2023 at 16:30
• @CraigFeinstein By "super polynomial subset", I meant to refer to "all instances of 3-SAT in which algorithm A takes super-polynomial time to run" Note that formally, a single instance is always solved in constant time if it is solved at all, so strictly speaking, such a set is always empty. But I assume you meant something different and it seems like my first interpretation was not correct, so I'm asking for a clarification. Mar 16, 2023 at 18:02
• @CraigFeinstein Indeed, thanks for the correction. Mar 19, 2023 at 10:56