Doug Klein (TAMUG) writes:

Yes, it is my guess that P does not equal NP. I do not have an insightful reason – I just suspect that with all the really sharp people who have looked at such problems (i.e., in NP) in lots of different contexts that if they coincided with P, then somebody would have found a solution in P in at least one of these (often very differently appearing) contexts. This then makes your approach to finding an efficient algorithm on a subset of graphs very reasonable – but I wonder how big a subset you imagine you are likely to find. Organic-molecular graphs (i.e., with all degrees <5) are an interesting subset, perhaps even important subset, having ~K^N members of N vertices, whereas the set of all graphs has ~~2^(N^2) members of N vertices. That is, this (important) subset is very small compared to the whole set.

# Organic-molecular graphs

Advertisements