Skip to main content
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
  • 162k
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
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
  • 162k
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
  • 759
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
  • 30.7k
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

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

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
  • 13.6k
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
  • 39.1k
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.6k
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
  • 162k
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

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

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

No, because you are supposed to choose the decision version so that any solution to the optimization problem can be used to solve the decision problem (with at most a polynomial increase in running ...
D.W.'s user avatar
  • 162k
2 votes
Accepted

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

I have now learned that this problem is co-NP-complete. The question can be reduced to testing whether a point in $R^{n^2}$ (given by the Gram matrix generated by the vectors) satisfies all the pure $(...
Alex Meiburg's user avatar
2 votes

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

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 ...
orlp's user avatar
  • 13.6k
2 votes
Accepted

Find all intervals that are contained in a query interval

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

Name of algorithm: When looking for an optimal element in a list, contionusly adapt the acceptance threshhold

These problems are in the field of optimal stopping theory. There are a large number of approaches to the problem, which can be found using this term. The example about dating appears in Hannah Fry's ...
Kjeld Schmidt's user avatar

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