Organic-molecular graphs

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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s