Question about the P versus NP Problem

Question

It seems to be an accepted belief based on decades of experience that naive algorithms are not adequate to solve NP-complete problems in a reasonable amount of time. Even those who believe P = NP seem to be looking for an algorithm with a very clever representation, so far without success.

Can the observations above be formalized? Let's use the full, unrestricted Clique problem as an example. Suppose it could be shown that no clever representation exists for the Clique problem. That is, suppose it could be proven for every algorithm that either:

1. the algorithm is correct and uses an internal representation such that no two distinct input cliques lead to the same internal representation, or
2. the algorithm is incorrect.

Would this be a worthwhile result? How important would it be? Or is it wrong?

Is there already a proof that CLIQUE or SAT, for example, cannot be solved in polynomial time by performing operations on cliques or Boolean expressions respectively?

References with your answer would be helpful. Thanks

Answer 1

You ask:

suppose it could be proven for every algorithm that either:

1. the algorithm is correct and uses an internal representation such that no two distinct input cliques lead to the same internal representation, or
2. the algorithm is incorrect.

Would this be a worthwhile result? How important would it be? Or is it wrong?

It's wrong. You can always take a correct algorithm for clique and add a preprocessing step that removes edges which are clearly not in any maximal clique. This will still be a correct algorithm for clique, and obviously does not satisfy either (1) or (2).

Answer 2

There are formal notions of Natural Proofs (Razborov-Rudich) and of proofs that relativize (Baker-Gill-Solovay) and both are known to not work for showing $P \neq NP$ . You are asking about relativizable algorithms, because any algorithm that works only on the "external shell" or "superficial interface" of SAT or Max-Clique will probably work equally in environments where Turing machines are connected to an oracle, and P=NP can be true or false depending on the oracle. At least for oracles with P < NP the algorithm will not run in polynomial time, and I think this is true for random oracles, so possibilities for SAT solvers that use only externally visible features to work in polynomial time are fairly limited.

There are also problems where algorithms that use only the external interface are outperformed by algorithms that take apart the internal representation of the data. For example, sorting by comparisons requires $n \log n$ operations compared to the linear-time radix sorting.