187 views
0 votes
0 votes

If P1 is reducible to P2,

then what does it exactly mean?

What should we assume  

  1. )   P1 is a subset of P2

                            or

       b.)   P2 is a subset of P1 

Please answer within the accordance that 

  1. If P1 is decidable then P2 may be decidable or undecidable.
  2. If P1 is undecidable then P2 is also Undecidable.
  3. If P2 is Undecidable then P1 may be decidable or undecidable.
  4. If P2 is Decidable then P1 will be definitly Decidable.

Please log in or register to answer this question.

Related questions

0 votes
0 votes
3 answers
1
Dknights asked Nov 9, 2022
505 views
what will be the DFA for RE – (a*ba)*
3 votes
3 votes
3 answers
2
BHOJARAM asked Dec 13, 2021
907 views
complement of CFL can never be CFL.please explain if the above statement is true of false?
0 votes
0 votes
1 answer
3
Nancy Pareta asked Jul 25, 2018
1,184 views
Dpda acceptance by empty stack is equivalent in power as dpda acceptance by final state?explain