179 views
0 votes
0 votes
"MATCH be the set of all graphs that have a perfect matching "

Is it decidable ?

My way of thinking :

Using Blossoms Theirem we can find whether graph  has matching set or not in polynomial time , But there is  no bound on Number of graphs then I think it is undecidable whether my graph has membership in MATCH.

Please help.

Please log in or register to answer this question.

Related questions

0 votes
0 votes
2 answers
1
Umeshkalal asked Dec 31, 2021
366 views
Regular expression for 0's and 1's that have odd no.of 1's
0 votes
0 votes
1 answer
2
Mayankprakash asked Dec 20, 2018
522 views
Do I need to study computability and decidability for gate 2019?Please suggest
0 votes
0 votes
1 answer
3
surbhijain93 asked Sep 7, 2018
2,589 views
Hi,Could someone please tell the difference between computability and decidability?Thanks
0 votes
0 votes
0 answers
4