cancel
Showing results for 
Search instead for 
Did you mean: 
cancel
464
Views
0
Helpful
0
Replies

Minimum Spanning Tree of Max Cost Complexity Class Problem

Marshall98
Level 1
Level 1

I am fair sure that it is in NP, as there is a way to 'guess' and verify that guess in polynomial time. But I am thinking that it is in P as well, as well use the Prim Algorithm within polynomial time as well.

If it is in both P & NP. Is it fair to say that it is in CoNP, RP & BPP as well? As P is a subset of CoNP, whereas RP is a subset of NP, & RP is also a subset of BPP. Is it fair to say that the problem above is in all of the 5 complexity classes - P, NP, CoNP, RP or BPP?
I am unsure if I misunderstood any of the concepts here. But please let me know if what I understand is correct. Thank you.

0 Replies 0