juanreutter
commented
2 years ago Cuando hablamos de complejidad la reducción siempre es polinomial, si.
Si sabes que L pertenece a C, entonces tienes la garantía que te da C, depende de la defincion de C. Osea si C es NP, tienes una maq de turing no det que funciona en tiempo polinomial, si C es exptime tienes una maq. deterministica que funciona en tiempo exponencial, y así.
Pero en general puedes abstraerte de eso: si L pertenece a C, entonces hay una máquina M que acepta a L que cumple con los requisitos de C, independiente de cuales sean. Y de ahí construyes sabiendo que como PTIME es subconjunto de C, agregarle más cosas polinomiales a M no cambia nada con respecto a C.
SebaHagedorn
Hola! tratando de hacer la demostración propuesta en los contenidos de la semana 10. Nos entregan 2 clases de complejidad C y C' tal que PTIME (subconjunto) C (subconjunto) C'. Sabemos además que un lenguaje L es C'-completo, por lo tanto para todo lenguaje L1 \in C' existe una reducción de L1 a L. Mi pregunta es: esta reducción es polinomial? o qué podemos concluir del tiempo de esta reducción debido a esto (PTIME (subconjunto) C (subconjunto) C')?
Además también me surgió la duda si que tenemos que este lenguaje L pertenece a C, sabemos que existe una máquina de Turing que acepta L. Qué sabemos de esta máquina? es determinista o no-det?
Muchas gracias por su respuesta