Skip to main content

New answers tagged

1 vote

Proof of NP-hardness: Is the problem of finding the minimum edge-weighted subgraph with at least M pairwise connectivity NP-hard?

This is still reducible from the k-minimum spanning tree problem. To reduce an instance, add a big number $W > \sum_{e \in E} c_e$ to every edge weights. Now, any optimal solution will use the ...
pcpthm's user avatar
  • 2,707
6 votes

If coNP ⊆ NP, does that mean coNP = NP?

Yes. Assume co-NP ⊆ NP. Take any NP problem. Its complement is co-NP, therefore NP by co-NP ⊆ NP, so the problem itself is co-NP, QED.
Jean Abou Samra's user avatar

Top 50 recent answers are included