Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
4  
This is perhaps better suited to cstheory.stackexchange.com –  Aryabhata Sep 14 '10 at 3:33
3  
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. –  Aryabhata 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

2 Answers 2

up vote 6 down vote accepted

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

share|improve this answer
    
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 –  ShyPerson 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? –  ShyPerson 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.