9 votes

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 ...
D.W.'s user avatar
  • 158k
8 votes

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 ...
David Richerby's user avatar
7 votes
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), (...
Albert Hendriks's user avatar
7 votes
Accepted

Choosing nonzero entries from an array so no pair in same row or column

The Birkhoff–von Neumann theorem states that a doubly stochastic matrix (a matrix with non-negative entries in which rows and columns sum to 1) can be written as a convex combination of permutation ...
Yuval Filmus's user avatar
6 votes

Efficient algorithm to decide if a location is reachable

The problem you're trying to solve is exactly graph connectivity. You don't necessarily need to construct the graph explicitly but this is a graph problem. By "you don't necessarily need to construct ...
David Richerby's user avatar
6 votes
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 ...
user2477759's user avatar
6 votes
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 ...
D.W.'s user avatar
  • 158k
5 votes
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 ...
rotia's user avatar
  • 749
5 votes
Accepted

Maximize ratio of sums

There's a linear-time algorithm for this problem. Find the index $j$ that maximizes the ratio $r_j = a_{1j} / a_{2j}$. This $r_j$ is the maximum possible value of the ratio of sums. Proof: The ...
D.W.'s user avatar
  • 158k
4 votes
Accepted

Efficiently locating the maximum value in interval over large amounts of data points

This can be solved with a balanced binary tree. Each such query can be answered in $O(\lg n)$ time. Build a balanced binary tree, where each leaf holds a point, and the tree is keyed on the $x$-...
D.W.'s user avatar
  • 158k
4 votes

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 ...
Carlos Linares López's user avatar
4 votes

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 ...
Reinstate Monica's user avatar
4 votes

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 ...
gnasher729's user avatar
  • 29.4k
4 votes
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 ...
Yuval Filmus's user avatar
3 votes

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 ...
orlp's user avatar
  • 12.9k
3 votes

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 ...
kelalaka's user avatar
  • 1,161
3 votes

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 ...
3 votes

Proving that a set of operations can't generate one integer from a given one

If you have implemented breadth first search correctly, you should have found that 1889 can be reached. $\quad 2019+7\to 2026$ $\quad 2026+7\to 2033$ $\quad\quad\cdots\quad$ (add 7 repeatedly) $\quad ...
John L.'s user avatar
  • 38.8k
3 votes

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

I think it's pretty easy to solve in O(n) time with one iteration over the array of integers representing the tree heights. You can only create valleys by your cuts, not hills, so you should count ...
Reducer's user avatar
  • 131
3 votes
Accepted

Does White never lose in Chess if Chess is solved?

This is unknown at the time of writing. Further, according to solving chess on Wikipedia, no resolution is expected in the near future.
Juho's user avatar
  • 22.5k
3 votes

Algorithm to create dense style crossword puzzles

There may simply be no solution to some of these problem instances. And the fact that the problem is NP-hard means that you cannot expect to find any efficient algorithm to find solutions for large ...
j_random_hacker's user avatar
3 votes

Does padding with dummy bits allow an NP-problem to be solved in fast exponential time?

Here is a more extreme example: $$ \mathrm{SAT_{PAD}} = \{1^{2^n} 0 \phi : \text{$\phi$ is a satisfiable CNF on $n$ variables}\}. $$ This language is decidable in polynomial time. What padding ...
Yuval Filmus's user avatar
3 votes
Accepted

Can a Turing machine quickly move to any position of a large string?

It depends. 1: If there are at least $\lceil \lg |s| \rceil$ unused cells after the end of $s$ and the head starts within $s$, then the answer is yes. Here is how. Start from the beginning of $s$. ...
D.W.'s user avatar
  • 158k
3 votes
Accepted

Strategy for searching for elementary cellular automata (cyclic boundary conditions) that repeat

Yes, all initial states under all CA rules on a finite grid will eventually lead to a cycle (or a fixed state, which can be viewed as a cycle of length 1). More generally, iterating any fixed ...
Ilmari Karonen's user avatar
2 votes

Efficient algorithm to decide if a location is reachable

From the comments on your post, being trapped means that you cannot reach every free space. You could run a simple depth first search (DFS) or breadth first search (BFS) on x. Each iteration, you ...
Ethan Yang's user avatar
2 votes

Choosing nonzero entries from an array so no pair in same row or column

As @YuvalFilmus says, this can be considered as the problem of finding a complete matching on a bipartite graph. The algorithm to do this is due to Hopcroft and Karp. Reference is Hopcroft and Karp, "...
vonbrand's user avatar
  • 14k
2 votes

Symmetry in Pattern Databases

From your question I assume you understand how symmetries are computed. As an exercise, make sure to understand the example given in Figure 4 which refers to the easiest of all symmetries, the Mirror (...
Carlos Linares López's user avatar
2 votes
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 ...
Yuval Filmus's user avatar

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