And the veil slid down: graph isomorphism

Definition courtesy of W|A: Screen Shot 2015-12-19 at 1.36.16 AM

Babai’s latest little gem causing a reasonable stir, as it was to be expected.

Wikipedia reminds us that in complexity theory, a decision problem is NPcomplete when it is both in NP and NPhard. The set of NPcomplete problems is often denoted by NP-C or NPC. The abbreviation NP refers to “nondeterministic polynomial time”.

 

Advertisements
Standard

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