# Tag Info

### Should you use Genetic algorithm for an extremly large unstructured search space?

No. Just knowing the size of the search space is not enough to tell whether GA will work or not. It also depends on the objective function (the "shape" of it), e.g., whether it is smoothly varying ...
• 159k

### Are there any optimization problems in P whose decision version is hard?

No. The optimization problem is "How big is the biggest $X$?" and the decision problem is "Is there an $X$ that is bigger than $y$?" Solving the decision problem simply involves ...
• 81.7k
Accepted

### Is there a polynomial time algorithm to determine whether an 'up down' language is 'emptible'?

Reduction from 3-SAT: a variable in 3-SAT becomes a character in your problem and is paired with its negation. Each clause becomes a word. e.g. 3 SAT: (a,b,-c) && (-b,c) => pairs: (a,-a), (...
• 2,521
Accepted

### Are there any optimization problems in P whose decision version is hard?

Maybe it depends on what it means by solving an optimization problem. If it is to find "how big is the biggest $f(x)$", then the answer is no (see the answer of @David Richerby). If it is to find "the ...
• 143
Accepted

### Minimum number of tree cuts so that each pair of trees alternates between strictly decreasing and strictly increasing

I'll describe two ways you could solve this problem. Either works. In some sense they are basically the same algorithm, just viewed from two different perspectives. Dynamic programming algorithm ...
• 159k
Accepted

### Can deterministic Turing machine beats/wins (if possible) the "Bombs and Levers" game in polynomial time?

Your problem is NP-hard. It is an easy proof In fact, it is NP-complete because we can reduce it to SAT in polynomial time We reduce 3-SAT to your problem. We have a lever for each variable and a ...
• 759

### Heuristics for the $n$-puzzle

First of all, a heuristic is said to be admissible if and only if $h(n)\leq h^*(n)$ for every state $n$, where $h(n)$ is your heuristic function and $h^*(n)$ is the cost of an optimal path from $n$ to ...
• 3,463

### Finding a local peak in an array in O(log N)?

To reformulate the question, there is the following problem: given an array of numbers, find an index in the array that is a local maximum, meaning the value at that index $\ge$ the values at adjacent ...

### Does White never lose in Chess if Chess is solved?

Let's take alternative chess. The rules are identical to chess, except that White can pass in it's very first move (but Black can't, even if White passed). Now it's obvious that White has a strategy ...
• 30k
Accepted

### Why do we use DAG rather than trees to represent search space of a search problem?

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 ...
• 277k

### Finding a local peak in an array in O(log N)?

No, it is not possible to find the max (peak) element in an unsorted array better than $\mathcal{O}(n)$. When you executed your algorithm $\mathcal{A}$ that has $c \log n$ compare operations, that ...
• 1,161

### search problem vs optimization problem

The fundamental difference in these two problems lies in the verification of a proposed solution. The solution of a search problem is only as hard to verify correct as the predicate itself. The ...
• 13.4k

### Find an element in sorted 2D-array (matrix)

(Copied from a post on StackOverflow) Here's a simple approach: Start at the bottom-left corner. If the target is less than that value, it must be above us, so move up one. Otherwise we know that ...

• 945

### Among $k$ unit vectors, find odd set with sum length less than 1

The latter problem feels similar to the Shortest Vector Problem (SVP) in integer lattices. The Shortest Vector Problem is: Input: vectors $v_1,\dots,v_k$ Goal: find a non-empty subset of vectors ...
• 159k
Accepted

### Is P = NP when solutions length is polynomially bounded by instance length?

You ask Doesn't polynomially bounding the length of possible solutions to a given instance mean that there are only polynomially many possible solution candidates? In fact, the number of binary ...
• 277k

### Fastest search algorithm in a sorted list with certain error rate-limiting constraints

For simplicity of analysis I will say that 'too high' is the error condition, which is just the problem inverted, $64^{64}-n$. I also assume that requests are instant. It takes some thinking, but ...
• 13.4k
You were too quick to reject interval trees and segment trees. You can search an segment tree for all intervals that are contained in a query interval $q=[\ell_q,u_q]$, using a straightforward ...