tesis de Cobham-Edmonds
question: ¿Qué hipótesis está asociada con la clase de complejidad de P vista como una abstracción matemática con funcionalidad algorítmica eficiente?, context: La clase de complejidad P es a menudo vista como una abstracción matemática modelando aquellas tareas computacionales que admiten un algoritmo eficiente. Esta hipótesis se llama la tesis de Cobham-Edmonds. La clase de complejidad NP, por otro lado, contiene muchos problemas que a las personas les gustaría resolver de manera eficiente, pero para los cuales no se conoce ningún algoritmo eficiente, como el problema de satisfacibilidad booleana, el problema del camino hamiltoniano y la cobertura de vértices. Dado que las máquinas de Turing deterministas son máquinas de Turing no deterministas especiales, se observa fácilmente que cada problema en P es también miembro de la clase NP.
¿Qué hipótesis está asociada con la clase de complejidad de P vista como una abstracción matemática con funcionalidad algorítmica eficiente?
la tesis de Cobham-Edmonds .
La clase de complejidad P es a menudo vista como una abstracción matemática modelando aquellas tareas computacionales que admiten un algoritmo eficiente. Esta hipótesis se llama la tesis de Cobham-Edmonds. La clase de complejidad NP, por otro lado, contiene muchos problemas que a las personas les gustaría resolver de manera eficiente, pero para los cuales no se conoce ningún algoritmo eficiente, como el problema de satisfacibilidad booleana, el problema del camino hamiltoniano y la cobertura de vértices. Dado que las máquinas de Turing deterministas son máquinas de Turing no deterministas especiales, se observa fácilmente que cada problema en P es también miembro de la clase NP.
la <hl> tesis de Cobham-Edmonds <hl> .
La clase de complejidad P es a menudo vista como una abstracción matemática modelando aquellas tareas computacionales que admiten un algoritmo eficiente. Esta hipótesis se llama la <hl> tesis de Cobham-Edmonds <hl>. La clase de complejidad NP, por otro lado, contiene muchos problemas que a las personas les gustaría resolver de manera eficiente, pero para los cuales no se conoce ningún algoritmo eficiente, como el problema de satisfacibilidad booleana, el problema del camino hamiltoniano y la cobertura de vértices. Dado que las máquinas de Turing deterministas son máquinas de Turing no deterministas especiales, se observa fácilmente que cada problema en P es también miembro de la clase NP.
La clase de complejidad P es a menudo vista como una abstracción matemática modelando aquellas tareas computacionales que admiten un algoritmo eficiente. Esta hipótesis se llama <hl> la tesis de Cobham-Edmonds . <hl> La clase de complejidad NP, por otro lado, contiene muchos problemas que a las personas les gustaría resolver de manera eficiente, pero para los cuales no se conoce ningún algoritmo eficiente, como el problema de satisfacibilidad booleana, el problema del camino hamiltoniano y la cobertura de vértices. Dado que las máquinas de Turing deterministas son máquinas de Turing no deterministas especiales, se observa fácilmente que cada problema en P es también miembro de la clase NP.