# Question about the P versus NP Problem

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?

• This is perhaps better suited to cstheory.stackexchange.com Sep 14 '10 at 3:33
• I don't consider this off-topic (although cstheory is a better site for it), am I wrong?
– anon
Sep 14 '10 at 9:13
• @muad: I didn't vote to close. I am not sure if this is off-topic, either. Sep 14 '10 at 15:18
• @Moron, oh sure, I wasn't implying that you did - I just wanted to know others opinion on whether it's appropriate here or not.
– anon
Sep 14 '10 at 16:23

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

• Mind if I ask a question? While it's clear that the preprocessing step can remove edges not in any maximal clique for very sparse graphs, for instance, what about difficult cliques which are, say, in the phase transition? Could you direct me to a polynomial-time algorithm for that? This gets to my question about incompressibility on cstheory-- can all graphs, even the most difficult ones like Turan graphs, be efficiently subjected to the compression being introduced by the preprocessing step? Thanks Mar 11 '11 at 5:26
• ... and if we can't get any compression on difficult graphs and restrict the inputs to only these graphs so as to make the preprocessing step into an identity transformation, does the original proposal get any traction? Especially if there is still an exponential number of incompressible graphs left over? Mar 11 '11 at 5:39

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.