Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

# Tag Info

3

Proving that $P= NP \cap$ co-$NP$ is an open problem and believed to be unlikely since Integer factoring decision problem is in both $NP$ and co-$NP$ but conjectured to be outside $P$.

2

I believe everything you said is correct. I note that your point #3 could hold regardless of points #1 and #2 - points #1 and #2 are just a concrete example of where this has provably happened.

1

A propositional proof system in which all tautologies have a "short" proof is called a super-propositional-proof system. Such a system exists iff NP = CoNP. If NP != CoNP then P != NP. So, it's not necessarily the only way to prove P != NP, but you could do so by proving a super-propositional-proof system cannot exist.

1

Jérôme, it seems to me that your initial confusion may be due to (unfamiliarity with) the different notions of Turing reduction and Karp reduction (at least, this was the case for me when I incurred into that very same confusion years ago; judging from your question and comments I can perceive my own flawed objections I had at that time). What you (seem to) ...

1

It might help to consider a different example. Given a number $n$, how would one succinctly prove that it is composite? Well, you can just provide a nontrivial factor. So COMPOSITES is obviously in NP. But given a number $n'$, how would you prove its not composite (i.e. prime)? That seems a lot harder. You can't just give a non-factor, you want to prove ...

1

The complementary version given by Wikipedia is correct. coNP consists of the complements of the problems in NP. In this case, the universe of discourse (i.e., the encoded instances) is the set of (properly encoded) graphs. The Hamiltonian cycle decision problem contains those graphs which are Hamiltonian; its complement is exactly the set of graphs which ...

Only top voted, non community-wiki answers of a minimum length are eligible