Register

Doubt : Computability

200 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.
User Avatar

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

426
views
2 answers
0 votes
Umeshkalal asked Dec 31, 2021
426 views
Theory of computability
Regular expression for 0's and 1's that have odd no.of 1's
User Avatar
585
views
1 answers
0 votes
Mayankprakash asked Dec 20, 2018
585 views
Computability and decidability
Do I need to study computability and decidability for gate 2019?Please suggest
User Avatar
2.7k
views
1 answers
0 votes
surbhijain93 asked Sep 7, 2018
2,719 views
Difference between computability and decidability
Hi,Could someone please tell the difference between computability and decidability?Thanks
User Avatar
596
views
0 answers
0 votes
hacker16 asked Dec 24, 2017
596 views
did P and NP is still in the syllabus? @ COMPUTABILITY AND COMPLEXITY{TOC}
did P and NP is still in the syllabus? @ COMPUTABILITY AND COMPLEXITY{TOC}
User Avatar
Link Copied!