
(Cartões) Complexidade: Classes P NP
Flashcard
•
Computers
•
University
•
Practice Problem
•
Hard
Fahad Kalil
FREE Resource
Student preview

8 questions
Show all answers
1.
FLASHCARD QUESTION
Front
O que é uma instância de um problema?
Back
Um caso particular ou exemplo do problema.
2.
FLASHCARD QUESTION
Front
Qual das seguintes afirmações sobre Classe P é verdadeira?
- NP é um subconjunto de P.
- P é um subconjunto de NP.
- P e NP são conjuntos disjuntos.
- Classe P admite soluções exponenciais.
Back
P é um subconjunto de NP.
3.
FLASHCARD QUESTION
Front
O que significa a abreviação NP em teoria da computação?
Back
"Nondeterministic Polynomial"
4.
FLASHCARD QUESTION
Front
A afirmativa: "Problemas intratáveis são aqueles para os quais o melhor limite inferior conhecido é polinomial, entretanto o melhor algoritmo conhecido é exponencial" é?
Back
Verdadeiro
5.
FLASHCARD QUESTION
Front
Se demonstrarmos que P=NP então:
Back
Todos os problemas NP passarão a fazer parte da classe P.
6.
FLASHCARD QUESTION
Front
Qual o papel de um certificado na demonstração de que um problema pertence a classe NP?
Back
Provar que uma solução é verificável em tempo polinomial.
7.
FLASHCARD QUESTION
Front
O que se deve demonstrar para um problema seja atribuído à classe NP?
Back
Que ao menos 1 instância do problema seja verificável em tempo polinomial.
Access all questions and much more by creating a free account
Create resources
Host any resource
Get auto-graded reports

Continue with Google

Continue with Email

Continue with Classlink

Continue with Clever
or continue with

Microsoft
%20(1).png)
Apple
Others
Already have an account?
Similar Resources on Wayground
6 questions
Questionário sobre Cirurgia do Pet Care
Flashcard
•
KG - University
7 questions
EMC Adriano, pessoa em situação de cirurgia
Flashcard
•
University
8 questions
Ferrugem Asiática da soja
Flashcard
•
KG - University
8 questions
Sistemas HVAC
Flashcard
•
University
5 questions
Flashcard sobre a Existência de Deus e a Natureza
Flashcard
•
KG - University
9 questions
PENSAMIENTO CRITICO
Flashcard
•
University
11 questions
Python [Basic]
Flashcard
•
KG
10 questions
Teste Ombording UFit
Flashcard
•
KG - University
Popular Resources on Wayground
7 questions
History of Valentine's Day
Interactive video
•
4th Grade
15 questions
Fractions on a Number Line
Quiz
•
3rd Grade
20 questions
Equivalent Fractions
Quiz
•
3rd Grade
25 questions
Multiplication Facts
Quiz
•
5th Grade
22 questions
fractions
Quiz
•
3rd Grade
15 questions
Valentine's Day Trivia
Quiz
•
3rd Grade
20 questions
Main Idea and Details
Quiz
•
5th Grade
20 questions
Context Clues
Quiz
•
6th Grade
Discover more resources for Computers
18 questions
Valentines Day Trivia
Quiz
•
3rd Grade - University
12 questions
IREAD Week 4 - Review
Quiz
•
3rd Grade - University
23 questions
Subject Verb Agreement
Quiz
•
9th Grade - University
5 questions
What is Presidents' Day?
Interactive video
•
10th Grade - University
7 questions
Renewable and Nonrenewable Resources
Interactive video
•
4th Grade - University
20 questions
Mardi Gras History
Quiz
•
6th Grade - University
10 questions
The Roaring 20's Crash Course US History
Interactive video
•
11th Grade - University
17 questions
Review9_TEACHER
Quiz
•
University