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:
- the algorithm is correct and uses an internal representation such that no two distinct input cliques lead to the same internal representation, or
- 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