Register

Decidable and undecidable problems

538 views
1 votes
1 votes
Please explain by giving example...

1.All undecidable problems are NP-Hard, but all NP-Hard problems are not undecidable.

2.NP and NPC problems can all be decided by a TM and hence are recursive.
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

0 votes
0 votes
1 answer
1
daksirp asked Jul 9, 2018
698 views
decidable and undecidable problem : https://gatecse.in/grammar-decidable-and-undecidable-problems/
Soutce : https://gatecse.in/grammar-decidable-and-undecidable-problems/ Why L(G1) ⋂ L(G2) = Φ ?? is undecidable for dcfl, cfl etc ?? please explain it anyone
Soutce : https://gatecse.in/grammar-decidable-and-undecidable-problems/Why L(G1) ⋂ L(G2) = Φ ?? is undecidable for dcfl, cfl etc ?? please explain it anyone
User Avatar
0 votes
0 votes
1 answer
2
ryan sequeira asked Feb 1, 2016
4,015 views
Decidable and Undecidable problems of automata
Please list down all the decidable and undecidable problems for FA, PDA, TM. Since there isnt a single place where all are listed.
Please list down all the decidable and undecidable problems for FA, PDA, TM.Since there isnt a single place where all are listed.
User Avatar
0 votes
0 votes
0 answers
3
Mk Utkarsh asked Sep 15, 2018
567 views
Decidable / Undecidable (Acceptance of CFL)
A Turing Machine accepts a language if its DCFL but rejects if it's a non deterministic CFL
A Turing Machine accepts a language if its DCFL but rejects if it's a non deterministic CFL
User Avatar
Link Copied!