4

A search algorithm is a recursive procedure which accepts an instance and a partial solution and attempts to extend it to a complete solution bit by bit. For example, consider a search algorithm trying to solve the eight queens puzzle. The search is initiated with an empty board. On any given position, the search algorithm attempts to place one more queen, ...


2

If the context-free grammar is unambiguous, you can count the number of sentences it generates in a linear scan with a carefully chosen order. I'll assume we have removed all useless symbols and cycles from the grammar. If it is finite and free of useless symbols and cycles, then it should not contain any recursion. Let $N(A)$ denote the number of sentences ...


2

This fails for, e.g., [1, 9, 55, 55, 100], t=111. The first iteration finds 110 and increases i to exclude 1 as a possibility, but the only solution, [1, 55, 55], needs 1. The basic problem is that when you increase i or reduce j, you are assuming that the element you just advanced past is not needed -- that there exists some solution that does not include ...


1

In terms of decidability, they are equivalent. Indeed, in order to turn a decision problem into a search problem we do the following: Run the decision algorithm If it outputted "no", return "no solution exists" Else, create a list called $Active$, and a counter $w\in\Sigma^*$. Until you find a solution, repeat the following 5-6 steps: ...


1

Here is an example of a search problem: Given a CNF $\varphi$, find a satisfying assignment $x$. Every satisfying assignment would do. A machine solves this problem if on input $\varphi$: If $\varphi$ is satisfiable, then the machine outputs a satisfying assignment. If $\varphi$ is unsatisfiable, then the machine outputs "unsatisfiable". An important ...


1

Here's a simple argument that the ability to find a witness in polynomial time would imply P=NP: Assume that we have a poly-time algorithm for finding a witness to any YES-instance of some NP-complete problem. Then there exist absolute constants $k$ and $c$ such that when run on a valid input of size $n$, the algorithm completes after at most $n^k + c$ ...


Only top voted, non community-wiki answers of a minimum length are eligible