Tag Info

New answers tagged decision-problem

2

I suspect that the question is looking for a non necessarily tight lower bound to the number of comparisons needed. The decision tree needs to be able to return the correct sorted sequence no matter what the initial permutation of the elements is. Therefore, it must have at least $n!$ leaves (one for each output permutation). Each internal vertex in the ...

3

In complexity theory, we often concentrate on decision problems. "Officially," NP-hardness is a category of decision problems — only a decision problem can be (or not be) NP-hard. However, it is also common to use NP-hardness when referring to optimization problems. An optimization problem is NP-hard if its decision version is NP-hard. In more ...

1

Now that you have edited your post, your question is more clear ('cause let's be honest, it was very confusing before the modifications…) By definition, problems in $NP$ are decision problems. However, $NP$-hard problems are not necessarily in $NP$ and even not necessarily decision problems. Let's make an example of this. Consider the following decision ...

1

If $E_{DFA}$ with input $C$ accepts, then $C = L(M) \cap B = \emptyset$. In other words, no word containing an odd number of 1s is also in $L(M)$. Then, by definition of $A$ you should accept. Conversely, if $E_{DFA}$ with input $C$ rejects, then $C = L(M) \cap B \neq \emptyset$. That is, there is some word $w \in L(M)$ such that $w$ contains an odd number ...

Top 50 recent answers are included