# Questions tagged [search-problem]

A class of computational problems. Where decision problems call for a yes-or-no answer, search problems are looking for an object satisfying a certain property.

118 questions
Filter by
Sorted by
Tagged with
58 views

145 views

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

If the machine has enough memory and speed as to compute all states of the Chess game in a reasonable time, can a player with the white pieces - operated by a machine - lose a game?
4k views

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

A gardener consider aesthetically appealing gardens in which the tops of sequential physical trees (eg palm trees) are always sequentially going up and down, that is: ...
15 views

### Beam search in the context of Genetic Algorithm

As per Machine Learning, Tom M. Mitchell, Indian Edition, pp. 249-262, it is mentioned that "genetic algorithms employ a randomized beam search method to seek a maximally fit hypothesis". I have ...
91 views

### Fastest algorithm to find whether a list contains a word?

Given an unordered list of words, what's quickest way to test whether a certain word is in that list? I can't think of another way to do this other than just going through each element in the list ...
33 views

### Breadth-first traversal: difference between generation and expansion

The question here is to find a path from A(rad) to B(ucharest). I'll be using the initials of the cities in the picture instead of their full names. Some ground-rules: we're traversing in ...
57 views

### I am looking for an algorithm that can find the best possible combination of inputs, in order to determine the optimum output

So as the title poorly implies, I'm looking for an algorithm that can accomplish the following task (as an example): Given the inputs A(1:100), B(1:100), C(1:100), that can take on any value between 1 ...
96 views

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

Given two numbers, $n$ and $m$, are there some mathematical methods of deducing $m$ from $n$ using limited number of elemantary operations? Example: 335 can be deduced from 2000 using division by 2, ...
94 views

### Efficient search for solving a Jigsaw Puzzle?

I believe that solving a Jigsaw puzzle is in general NP-complete based on the two questions linked below. However, I'd like to implement a heuristic algorithm that works well in practice. Let's ...
29 views

### Hardness of FNP vs Choice of Verifiers

A (T)FNP problem is induced by a NP language, say $L$. Usually in the notion of verifers, we define $L=\{x:\exists y,V(x,y)=1\}$, where $V$ is a poly-time verifier. The function version would be ...
72 views

### Repeated String Match: need help to understand the maximum number of repeats needed to be looked at

There's this question on LeetCode (link): Given two strings A and B, find the minimum number of times ...
960 views

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

Given an $N\times N$ array, where elements are decreasing in every row and every column. What is the fastest way to find the $(i,j)$ of a given element if it exists in the array, or return no if it ...
162 views

### Interesting logic problems

I've just began a course on logic and learned the following : De Morgan's laws Normal forms How to represent a logical formula (using or, and, not operators) using binary trees How to get the ...
145 views

### Search on Conformant Problem: solution for subset of a belief state

I am having trouble understanding the following statement. I have understood why in a sensorless/conformant problem, if there exists a solution (a sequence of actions) for a belief state $b$, then it ...
89 views

### How to accomodate decision trees with infinite options

I know that once I have a graph or decision tree representation of a problem, there are many different ways I can get a computer to solve the problem. They're called search algorithms, and go by names ...
20 views

### fastest way to find matching pattern

I have several series of integers (vectors) that could be plotted at equal distances apart: ...
263 views

### Efficient way to find matching date ranges?

We have a set of problems involving date ranges - a pair of dates representing a start date and an end date. In some places, we have say 1000 of these and need to find the ones that overlap a separate ...
116 views

### String Search - how to find the “most” accurate string?

Assume I have the following list of companies: Apple Big Apple Google Then I have this sample string: Big Apple is a company that is trying to be the next Google. Given the list of companies and ...
253 views

### reducing a decision problem to a local search problem

Lemma 4 in How easy is local search by Johnson, Papadimitriou, and Yannakakis, states: If a PLS problem is NP-hard then NP = P So assuming L is a PLS problem (polynomial local search problem) that ...
1k views

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

So I watched a couple of videos regarding this and the divide and conquer made sense to me. But I am still not convinced as to how recursing on the side with the larger number guarantees us the ...
240 views

### Algorithm to organize a tournament where the team componentes change each round

So, I was tasked with creating an app that generates the schedule of a doubles tennis tournament (i.e., teams of two) in a way that, by the end of it, everyone would have played against the rest of ...
23 views

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

I'm looking for one of two closely related algorithms. In both, you have a list of elements, of which you have to choose one by some scoring method. In the first variation, the list is infinite and ...
1k views

### Babyface vs Heel

So here's the question: "There are two types of professional wrestlers: "babyfaces"("good guys") and "heels"("bad guys"). Between any pair of professional wrestlers, there may or may not be a rivalry. ...
18 views

### Search techniques to find desired output with complex interdependencies

I am trying to generate output consisting of three-tuples (A,B,C), where A,B, and C are three different datatypes representing different values. I also have a collection of functions $f_i \in F$ ...
323 views

### search problem vs optimization problem

This is mostly a terminological question: Is there a fundamental difference between "optimization problems" and "search problems"? Apologies if this is an obvious question As I ...
60 views

### Give a Search Problem in co-NP

Ex.1. Give a Search Problem whose deciding Problem is in co-NP. Assuming 3SAT is in NP then asking wether a given Boolean formula has a Solution is a search problem in NP right? Then would asking ...
57 views

### Alternatives to evolutionary computing for structure, design and policy optimization (optimal structure search)?

I once had this question https://math.stackexchange.com/questions/1083338/structural-design-meta-optimization-is-there-mathematical-theory-optimiza about the methods for finding optimal structures, ...
617 views

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

Normally to show that an optimization problem is hard, we show the corresponding decision version of the problem is hard. However, is this sufficient to support the conclusion? Does there exist any ...
101 views

### Is there an analysis of the creation of axioms for a mathematical structure as a computational problem?

Historically, what has happened is the following: There is a "mechanical" structure, most importantly, arithmetic, which operates according to a set of well-defined rules that a stupid computer can ...
170 views

### How to minimize the sum of edge weight in the graph while keep the all-pair shortest path greater than a constant?

For example, if we have a graph G = (V, E) and a subset of vertices $U \subset V$. We can set $w(e)$ where $e \in E$ to be a non-negative real number. We want to minimize the total edge weight, but ...
33 views

### Algorithm Suggestion for periodic alerts

I am making a webapp that alerts when product prices fall or rise above a number. Let's say a product costs 100 and the user wants to be alerted when it reaches 80, the prices change every hour or so ...
41 views

### Reducing amount of possible states solving Pacman by searching

I consider simplified Pacman game: movement is discrete (on the grid), ghosts move deterministically based on difference between their and Pacmans coordinates, ghosts move every second turn, ghosts ...
68 views

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

I have $k$ unit vectors in $\mathbb{R}^k$. Can I efficiently identify a set of $2n+1$ vectors $v_1, \dots v_{2n+1}$ such that $\sum_{i< j} v_i\cdot v_j < -n$ for any $n$ -- or determine that no ...
48 views

### What data structure should I use for storing my data?

I am currently looking for a way in which I can store my data, and quickly look it up. What currently seem to be the best idea is to use a hash map. reasons: To identify what item I am looking for, ...
267 views

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

The description of this game is already exists in this link I am quoting from this link the description of the game to ease the reading of this question: In a game, where there are m active bombs, ...
Given a set of intervals $S = I_1, ..., I_n$, what is the fastest way to find all intervals of $S$ that are completely contained in an interval $I_\text{query}$? It should also support incremental (...