Hi, I've a question about Chapter 10:
Do classes P and NP belong strictly to REC? Or they can fall outside of it?
And what about NP-hard?
Thanks in advance
P and NP are languages that can be decided by TMs that halt both for positive and negative answers. Therefore these languages are all in REC.
There are languages in REC that are even more difficult than NP. Therefore inclusion is strict. Problems in REC - NP are called NP-hard.
It is also very common to call NP-hard problems that are similar to NP-complete problems, but are not decision problems: they are search / optimization problems, that is, the output is not just yes/no.
Hope this helps!
Got it, thanks.
So for any language that belongs to REG or CFL we can directly say that there is for sure a TM able to recognize it in polynomial time, without explaining the structure or the functioning of the TM in question, correct?
(My question stems from the way in which points c and d of exercise 4 of the exam of 25/01/23 were carried out)
So for any language that belongs to REG or CFL we can directly say that there is for sure a TM able to recognize it in polynomial time, without explaining the structure or the functioning of the TM in question, correct?
(My question stems from the way in which points c and d of exercise 4 of the exam of 25/01/23 were carried out)
Yes correct. More precisely, we have presented algorithms for the membership problem for REG and for CFL, and have observed that those algorithms work in polynomial time on a standard computer. We have also mentioned in some lecture that if a problem is polynomial time in a standard computer, then it is polynomial time for TM.