Difficult Problems Flashcards
What are the Hardest problems?
They cannot be solved at all
What is an extremely hard problem?
Problems that need at least exponential time, measured in the length of input
What is an NP-Hard problem?
A problem that is at least as hard as the hardest problems in NP
What is the definition of a decision problem?
They are defined by a set of possible inputs, for each input a set of correct outputs where each output can either be a yes or no
What are some observations about decision problems?
They are particularly simple
Some are natural decision problems
All problems where solutions have a quality have a decision variant
What is the formal definition of the NP problem class?
An algorithmic decision problem belongs to the class NP if for every input I of length n with output ‘yes’ there exists a certificate c(I) of length at most p(n) such that there is an algorithm that given I and c(I) can verify that I is a ‘yes’ instance in time at most p(n) for some polynomial p
What does a problem being an NP problem mean in simple terms?
- For a yes input, there exists at least one certificate that enables us to check that the input is actually a ‘yes’ input in polynomial time
- For a no input, considering all possible certificates, none can convince us that the input is a ‘yes’ input
What do we mean by a certificate? (in the definition of the NP class)
A proof that shows that I is a ‘yes’ input
What is an example of an NP problem?
The knapsack problem
What is the formal definition of the P class of problems?
An algorithmic problem belongs to the class P if there is an algorithm that computes a correct output for every input I with length n in time at most p(n) for some polynomial p
