1
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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

$\endgroup$
12
  • $\begingroup$ 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. $\endgroup$ Mar 16, 2023 at 16:04
  • $\begingroup$ 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? $\endgroup$
    – Discrete lizard
    Mar 16, 2023 at 16:18
  • $\begingroup$ I don’t think I said “super polynomial subset”. Super polynomial means something like exponential. It seems like you are misunderstanding my question. $\endgroup$ Mar 16, 2023 at 16:30
  • $\begingroup$ @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. $\endgroup$
    – Discrete lizard
    Mar 16, 2023 at 18:02
  • 1
    $\begingroup$ @CraigFeinstein Indeed, thanks for the correction. $\endgroup$
    – Discrete lizard
    Mar 19, 2023 at 10:56

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.