NP is proper subset of recursive which is in turn a proper subset of REL. src: https://cs.stackexchange.com/questions/90659/what-is-the-relation-between-np-np-hard-problems-and-recursive-r-e-languages-an

The Gateway to Computer Science Excellence

+2 votes

0

0 votes

i think every problem in NP is decidable means it is recursive .and every recursive problem is recursively enumerable so we can say that both are true,correct me if i am wrong ..

0

@Sidhi: Sir,

I have a doubt what does "every problem in NP is decidable " means?

What we are deciding for given NP problem?

Are we deciding proposed solution is correct or not?

Or are we deciding whether any solution exists for given problem?

Sorry, if I asked a lame question :P

0

i can't understand what you want to ask exactly..may below link will help you to understand, check it out.

https://www.quora.com/Theoretical-Computer-Science-Are-all-P-languages-decidable-Are-all-NP-languages-decidable

https://www.quora.com/Theoretical-Computer-Science-Are-all-P-languages-decidable-Are-all-NP-languages-decidable

+1

@Sidhi: thanks for that wonderful link.. Concept is pretty clear now!!

- NP is the class of languages that can be recognized by a non deterministic Turing machine
- A decidable language is a formal language for which there exists a Turing machine which will, when presented with any finite input string , halt and accept if the string is in the language, and halt and reject otherwise.
- Since any language in NP can be recognized by a non deterministic TM, there is a TM that always halts when presented with any finite input string of the language.
- Hence NP is decidable
- Since P⊂ NP, any language in P is also decidable.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,309 answers

198,330 comments

105,019 users