complexity theory - Is the complement of the language CLIQUE element of NP? -


i'm studying np class , 1 of slides mentions:

it seems verifying not present more difficult verifying present.        ______                  _________ hence, clique (complement) , subsetsum (complement) not members of np. 

was ever proved, whether complement of clique element of np?

also, have proof?

this open problem, actually! complexity class co-np consists of complements of problems in np. it's unknown whether np = co-np right now, , many people suspect answer no.

just clique np-complete, complement of clique co-np-complete. (more generally, complement of np-complete problem co-np-complete). there's theorem if co-np-complete problem in np, co-np = np,which huge theoretical breakthrough.

if you're interested in learning more this, check out the wikipedia article on co-np , around online more resources.


Comments

Popular posts from this blog

get url and add instance to a model with prefilled foreign key :django admin -

css - Make div keyboard-scrollable in jQuery Mobile? -

ruby on rails - Seeing duplicate requests handled with Unicorn -