Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

3
votes
1answer
23 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 ...
1
vote
1answer
26 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 ...
0
votes
1answer
54 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 ...
3
votes
2answers
92 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 ...
1
vote
1answer
34 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 ...
0
votes
0answers
24 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 ...
1
vote
0answers
17 views

fastest way to find matching pattern

I have several series of integers (vectors) that could be plotted at equal distances apart: ...
0
votes
2answers
60 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 ...
0
votes
1answer
71 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 ...
1
vote
1answer
37 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 ...
2
votes
2answers
177 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 ...
1
vote
1answer
81 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 ...
1
vote
1answer
20 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 ...
0
votes
1answer
176 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. ...
0
votes
0answers
16 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$ ...
3
votes
1answer
77 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 understand it, we can ...
1
vote
1answer
48 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 ...
0
votes
1answer
24 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, ...
4
votes
4answers
484 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 ...
2
votes
0answers
97 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 ...
3
votes
0answers
79 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 ...
0
votes
0answers
30 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 ...
0
votes
0answers
39 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 ...
4
votes
2answers
55 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 ...
3
votes
0answers
40 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, ...
6
votes
1answer
255 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, ...
4
votes
1answer
194 views

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

This problem came up during the Google CTF 2017. For background information about the challenge you can search for GoogleCTF A7 ~ Gee cue elle. Problem description:...
1
vote
1answer
662 views

Find all intervals that are contained in a query interval

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 (...
6
votes
1answer
253 views

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

Definitions: An up down language is a language whose alphabet is a set of pairs, but not characters, of two characters, where the one character in the pair is the opposite of the other character in ...
6
votes
1answer
826 views

(Nontrivial) Algorithms for finding the third largest element of a set

According to the lecture note by Jeff Erickson, the lower bound for finding the third largest element of a set of $n$ distinct elements is open. See the related post: What is the lower bound for ...
0
votes
0answers
729 views

NP Completeness: definition of search problem: Existence and Infinite Search space

For NP completeness proofs/reductions, I need to establish that the problem is a "search problem"... However, the definitions seem to be somewhat vague. If the definition of the search problem is: ...
2
votes
2answers
131 views

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

I'm currently reading the book "P, NP, and NP-Completeness" by Oded Goldreich. I'm currently reading a chapter that's concerned with the "search version" of the P-vs-NP-problem, that is if finding ...
1
vote
1answer
836 views

Heuristics for the $n$-puzzle

An admissible heuristic for an n-puzzle is the Manhattan distance. Now if the cost of a transition is equal to the number of the piece that is moved, is it true that the Manhattan distance is still an ...
1
vote
1answer
200 views

MAX SAT Optimization problem

search problem: find the assignment that maximize the number of satisfied clauses For decision problem: determine whether there is an assignment that satisfies k of clauses. optimization problem : ...
1
vote
0answers
49 views

What's the name of this problem? (Search for minimal satisfying sets)

NB: I've been trying to Google for prior work on the problem described later in this post, but the search results I get for all the keywords I can come up with (e.g. ...
1
vote
1answer
919 views

Why do so many 8-Puzzle solving algorithms use DFS instead of BFS?

I see so many 8 Puzzle Solvers use a stack instead of a queue. Why is that? If you are looking for the solution with the fewest number of moves, wouldn't the solution be at a shallower point in the ...
2
votes
0answers
83 views

Generating a distinct k-partition of n

Let us consider a specific case of an extended Kakuro puzzle. Given an integer $n$, we must form $n$ as the sum of $k$ distinct positive integers each less than or equal to $r$. From a mathematical ...
6
votes
1answer
558 views

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

My search space is discrete and in the order of $10^{1360}$, with a probably very complex fitness surface. Is it hopeless to attempt to use GA for such a problem? One fitness evaluation could take 1-3 ...
5
votes
1answer
99 views

Partitioning an undirected, unweighted, square planar graph paths that join certain pairs of nodes

I am trying to find a way to efficiently solve a puzzle that I play a lot by turning it into a graph partitioning problem (which is basically is in its actual form). I know that generally, graph ...
3
votes
2answers
87 views

Symmetry in Pattern Databases

I am trying to understand the use of symmetry in pattern databases (Heuristics, single agent search). This is too specialized of a topic to find common videos or explanations in general. I read the ...
1
vote
0answers
32 views

Classification with optional/catchall attributes

Context Let $S$ be a set of objects, each object $S_k$ containing a set of attributes $A_k\subseteq A$, where $A$ is a global set of attributes. Suppose each attribute $a_k\in A$ can take on integer ...
1
vote
1answer
506 views

Reduce set partition search to decision?

I'm a little lost and don't know how to approach this problem. Show the partition search problem can be poly-time reduced to the partition decision problem, the partition decision problem takes ...
1
vote
0answers
68 views

Neighbourhood design in Variable Neighbourhood Search

Variable Neighbourhood Search (VNS) is a metaheuristic for solving (combinatorial) optimization problems. It iteratively explores growing neighbourhoods to find better local optima in each iteration. ...
1
vote
0answers
45 views

An optimization in this algorithm

I'm trying to implement an autocomplete feature for a search engine. I have a database of words(stemmed) that occur in the documents that I have. what I'm doing is: Constructing a graph with words as ...
1
vote
1answer
159 views

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

I have a set of $n$ two-dimensional data points $(x_i,y_i)$. I want to efficiently answer the following query: Given an arbitrary interval of $x$-values, find the highest and lowest points within ...
3
votes
1answer
249 views

Informed search with a lower-bound heuristic?

I am well aware of informed graph / tree search strategies for optimal solutions when one has an admissible heuristic - i.e. one that never overestimates the minimum cost from a node to any goal state....
1
vote
0answers
122 views

How can I solve this problem which seems related to the Kth-heaviest subset problem?

Instance: Given a matrix of size $m\times n$ of positive real numbers, $m$ real numbers $L_i$ for all $i\in\{1,\cdots,m\}$ and an integer $k$ less or equal than $n$. Question: Is there a subset of ...
2
votes
1answer
283 views

Maximize ratio of sums

I have a $2 \times n$ matrix of positive integers, where the elements are denoted by $a_{ij}$ for all $i$ in the set $\{1,2\}$ and for all $j$ in the set $\{1,\ldots,n\}$. I would like to select a ...
3
votes
2answers
90 views

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

Suppose we have an $n\times n$ array $A$ of non-negative real numbers in which the sum of each row and each column is $1$. We want to find $n$ entries of the array $(x_1,y_1), \dots, (...
2
votes
3answers
165 views

Efficient algorithm to decide if a location is reachable

I am designing a game solver. I have a binary $m*n$ Matrix, where $0$ stands for a free space, while $1$ stands for an occupied space. In the game we move a ball that we will call $x$. The ball can ...