Collect interesting or clever proofs of specific instances of NP-complete problems being proved to have no solution. Inspired by proofs that certain graphs have no Hamiltonian path, where the general Hamiltonian path or cycle problem is NP-complete. Also easily applicable to satisfiability.
We're probably wandering into co-NP.
A proof that a problem has no solution done by enumerating all possibilities is mundane (and exponentially long (actually just super-polynomial), by the nature of NP). Interesting proofs avoid the exponentiality. Such proofs, perhaps many taken together, might provide insights into the nature of class NP, of course aiming for resolving the P versus NP problem. Ultimately we are looking for indications that there exist problems for which one cannot avoid exponential computation to prove there is no solution.
Conversely, a solution to a specific NP (not NP-complete) problem (for which no polynomial time algorithm is originally known) found by brute force is mundane. Solutions found in a way that generalizes to polynomial-time are interesting, essentially proving that the problem is in P. Collecting many such proofs may be useful. Again, we are looking for commonalities in ways problems get interestingly proven to be in P.
No comments :
Post a Comment