Clases de complejidad

Clases de complejidad

University

10 Qs

quiz-placeholder

Similar activities

Parcial 1, Primera serie

Parcial 1, Primera serie

6th Grade - University

10 Qs

Aprendeu ou disfarçou?

Aprendeu ou disfarçou?

12th Grade - Professional Development

10 Qs

Identify Loci!

Identify Loci!

10th Grade - University

8 Qs

UX Design

UX Design

University

10 Qs

Quizz Internet

Quizz Internet

KG - Professional Development

12 Qs

Archivos Digitales

Archivos Digitales

9th Grade - University

14 Qs

Chapter 3 Exploring Linux Filesystems

Chapter 3 Exploring Linux Filesystems

11th Grade - University

10 Qs

Día de la familia

Día de la familia

University

10 Qs

Clases de complejidad

Clases de complejidad

Assessment

Quiz

Computers, Mathematics

University

Practice Problem

Hard

Created by

Víctor Podberezski

Used 1+ times

FREE Resource

AI

Enhance your content in a minute

Add similar questions
Adjust reading levels
Convert to real-world scenario
Translate activity
More...

10 questions

Show all answers

1.

MULTIPLE CHOICE QUESTION

30 sec • 5 pts

Un problema es P si se demuestra que puede resolverse en tiempo “polinomial”

Verdadero

Falso

2.

MULTIPLE CHOICE QUESTION

30 sec • 5 pts

Un problema es NP si se demuestra que NO puede resolverse en tiempo “polinomial”

Verdadero

Falso

3.

MULTIPLE CHOICE QUESTION

45 sec • 5 pts

Una reducción polinomial ...

Corresponde a la transformación de un problema tratable (polinomial) en otro cuya resolución algorítmica se conoce

Corresponde a reducir la complejidad de un problema NP a uno P para resolverlo en tiempo polinomial

Únicamente se aplica a problemas de decisión y permiten determinar si un problema pertenece a la clase NP-Completa

Consiste en una doble transformación de tipo polinomial de una instancia de problema en otro y luego de la solución a la solución del problema original

4.

MULTIPLE CHOICE QUESTION

45 sec • 5 pts

Un certificador polinomial

Es la segunda transformación de una reducción polinomial que evalúa la solución encontrada

Es la solución a una instancia de un problema NP-C

Es un algoritmo que resuelve un problema de decisión en tiempo polinomial

Es el algoritmo polinomial que determina si una solución es válida para una determina instancia de un problema

5.

MULTIPLE CHOICE QUESTION

30 sec • 5 pts

Un problema puede ser NPH (NP Hard) y NP a la vez

Verdadero

Falso

6.

MULTIPLE CHOICE QUESTION

45 sec • 5 pts

Cuál de las siguientes afirmaciones no se puede realizar para la clase de complejidad P

Alcanza que exista un algoritmo que resuelva el problema en tiempo polinomial para considerar ese problema perteneciente a P

Existen problemas en NP-C que puedan reducirse en tiempo polinomial a un problema P

Está demostrado que si el problema pertenece a P entonces también pertenece a NP

Está demostrado que el problema para pertenecer a P se debe poder resolver utilizando una complejidad espacial polinomial

Ninguna de las anteriores

7.

MULTIPLE CHOICE QUESTION

45 sec • 5 pts

Sabiendo que un problema A es NPC (NP Completo) y que el problema A puede resolverse con una instancia de otro problema B, cuál de las siguiente afirmaciones NO podemos afirmar que sea correcta?

B es P

B es al menos tan difícil que A

B es al menos NPH

Si B es NP, entonces es NPC

Create a free account and access millions of resources

Create resources

Host any resource

Get auto-graded reports

Google

Continue with Google

Email

Continue with Email

Classlink

Continue with Classlink

Clever

Continue with Clever

or continue with

Microsoft

Microsoft

Apple

Apple

Others

Others

Already have an account?