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.

learn more… | top users | synonyms

2
votes
2answers
47 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
20 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
58 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
12 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
39 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 ...
1
vote
1answer
134 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
19 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 ...
0
votes
0answers
102 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 ...
1
vote
1answer
86 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
69 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
113 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 ...
0
votes
0answers
26 views

Optimal shortest path: When heuristic overestimates

Is it possible (or does there exists a special case) where the optimal shortest path is guaranteed even where the heuristic function always overestimates? Intentions for such a query : Trying to ...
6
votes
2answers
215 views

Is there any strategy to brute force search?

I don't know how to state it elegantly, but basically, I want to implement a brute force search algorithm, but there are many different ways that I could enumerate through the search space. This ...
2
votes
1answer
182 views

Finding median of three sorted array (the same length)

I think about following problem: There are given three sorted arrays $A,B,C$ (each of them is length $n$). Every array has distinct elements. Find median of union $A,B,C$. I consider following ...
4
votes
5answers
2k views

Algorithm for finding two smallest numbers in an array

I was just thinking today that the best approach to find two smallest numbers in any array would be to first sort(ascending order) it with some efficient algorithm like ...
4
votes
1answer
80 views

What is the complexity of finding a regular expression equivalent to a given DFA?

I had taken a course long ago on complexity theory. I only remember basic things, so I am reading "Introduction to the Theory of Computation by Michael Sipser". The book in its first chapter ...
7
votes
1answer
133 views

Find the central point in a metric-space point set, in less than $O(n^2)$?

I have a set of $n$ points which are defined in a metric space – so I can measure a 'distance' between points but nothing else. I want to find the most central point within this set, which I ...
2
votes
1answer
78 views

Showing NP-hardness by reducing from a search problem

I'm comfortable with showing NP-completeness of a decision problem: just take some problem that is known to be hard and reduce it to your new problem. This establishes NP-hardness of the new problem. ...
0
votes
0answers
59 views

Find all sets of n unique rows in matrix

I am looking for an efficient method to find all unique combinations of $n$ rows in a matrix. For example, if $n=6$, then I want to find all sets of 6 rows from the input set C in which the columns ...
-3
votes
1answer
229 views

Write an algorithm that finds array elements that sum up to some value [closed]

The following is a pseudo-code named PractOne. It takes a finite list A of real numbers and gives the pair ...
1
vote
1answer
109 views

Solving cycle in undirected graph in log space?

Setting Let: $$UCYLE = \mathcal \{ <G> ~:~ G \text{ is an undirected graph that contains a simple cycle}\}.$$ My Solution we show $UCYLE \in L$ by constructing $\mathcal M$ that decides ...
7
votes
1answer
188 views

Searching the space of permutations

I'm given n objects, and a set of n permutations of these n objects (out of n! total permutations). There is a true underlying permutation, which I know is one among the set of n permutations, but I ...
2
votes
1answer
101 views

Weighted closest-pair-of-points problem

I want to solve the following optimisation problem (an approximation or heuristic would be helpful as well). I have two sets of points in the plane: $P=\left\{ p_{1},p_{2},\dots,p_{N}\right\} $ and ...
4
votes
1answer
252 views

Does NP-completeness require to find the solution?

In the paper "Computing Equilibria:A Computational Complexity Perspective" by Tim Roughgarden, they consider the problem: Problem 2.1 (Clique). Given a graph $G = (V, E)$ and an integer $k$: if ...
2
votes
0answers
29 views

Proof sketch that NP total search problems cannot be NP-complete [duplicate]

From a blog post, about proving that NP total search problems cannot be NP-complete unless NP=co-NP. It's possible to write a convincing proof sketch as follows. Consider what would it would mean ...
3
votes
1answer
72 views

Are there name and literature for this SAT-like problem?

Given $f : \{0,1\}^* \to \{0,1\}$ and $n \in \mathbb{N}$, we define $\textsf{Prob}(f,n)$ as the following problem: Find an $x \in \{0,1\}^n$ such that $f(x) = 1$. A machine solving ...
0
votes
1answer
70 views

Searching through a heap complexity

Pretend you want to search through a max-heap to find a specific element. I know there is no such option but still... Would it take worse case O(n) or O(logn) time? I am assuming O(n) since the ...
9
votes
4answers
338 views

Can finding a witness be NP-hard even if we already know there is one?

The common examples of NP-hard problems (clique, 3-SAT, vertex cover, etc.) are of the type where we don't know whether the answer is "yes" or "no" beforehand. Suppose that we have a problem in which ...
0
votes
0answers
201 views

Finding longest subsegment of array having certain property

Assume we are given an Array[0,N) of N integers A [0], A[1], ... A[N-1] and a boolean function Bad(n) that examines consecutive elements A[n], A[n+1], A[n+2] for some property of "badness". For ...
2
votes
3answers
84 views

Graph cycles on 40 vertices

I'm trying to create an algorithm in polynomial time, that detects wether or not a graph is in a language. The language specifies that a graph is only part of this language if it has a cycle on 40 ...
0
votes
0answers
157 views

What data structure would help find nearby coordinates quickly?

I need to write a program that does the following: Take an input list of objects whose properties include latitude and longitude to, say, 5 decimal places Store them in a data structure once Provide ...
1
vote
1answer
444 views

Artificial intelligence - bridge and torch problem

I am doing a artificial intelligence course as part of my computer science degree. I am stuck on a question about searching. The question is a version of the Bridge and torch problem. Five people ...
0
votes
1answer
142 views

Efficiently count frequency of n-grams at start of words

I have a text file with all possible 5-grams (26^5 = 11.881.376) organized in rows as: aaaaa aaaab aaaac aaaad ..... and I have a txt file (organized in rows) with all English words. I have to find ...
1
vote
1answer
243 views

How to do high performance string matching when comparing unordered sets of tokens [closed]

This is the problem: I have some strings stored in the database. Each of the strings can be seen as a set of tokens separated by comma with no repetition (I mean a token cannot appear more than one ...
1
vote
1answer
67 views

Using A* search with different heuristic values

I am currently trying to use A* to create cyclical routes (for plotting driving routes of set distances). I want to find a driving route from my start location that is as close to my specified length ...
0
votes
1answer
264 views

Selection problem on the union of two ordered dictionaries

Suppose we are given two ordered dictionaries S and T each with n items, and that S and T are implemented by means of array-based ordered sequences. Describe an O(log n) time algorithm for finding ...
2
votes
1answer
89 views

What is the lower bound for finding the third largest in a set of $n$ elements?

The problem is easy to describe: What is the lower bound for finding the third largest in a set of $n$ elements? Particularly, do we have to know both the largest and the second largest for ...
2
votes
1answer
56 views

Whats the name of this search game?

I am struggling in finding the name of this game (in order to find research papers related to it in the literature). Given an initial word $X$ and a target word $Y$, what is the minimum number of ...
1
vote
1answer
72 views

Generating hard puzzles for a backtracking snake

Let $M$ be a matrix of height $h$ and width $w$. Each entry of $M$ is an integer. There is a snake that starts from the "left side" of $M$, and its goal is to reach the "right side" of $M$. To get ...
4
votes
1answer
401 views

Finding an element in a sorted array with at most three queries to larger elements

Given a sorted array A, we have to find the position of an element m in it. (It is also given that the element exists in the array.) However there is a constraint. Like in a game you have 3 lives. If ...
0
votes
2answers
65 views

Given a graph, finding if a node has three adjacents from a node subset $N$

Given a graph $G = (V,E)$, assume that we have two disjoint vertex sets $N = \{n_1, n_2 ...\} \subset V$ and $P = \{p_1, p_2, ...\} \subset V$ such that $N \bigcup P \neq V$. I want to find if there ...
0
votes
0answers
51 views

TF-IDF query engine in context of terms weight

I'm looking for public algorithm which gives the engine these abilities: Query by ranked terms Limit outcome by date/time range Basically, i'd like to concentrate articles (generally ...
1
vote
1answer
684 views

Time complexity of 8-queen, by placeing one by one without attack

I am new to artificial intelligence. I have been trying to analyse the time complexity of 8-queen, by placing one by one without attack. One approach to achieve goal state is to "add a queen to any ...
0
votes
1answer
40 views

How feasible is it for a non-distributed web crawler running on consumer hardware to search the internet? [closed]

I am looking for an automated way to answer the question: what are the URLs on the world wide web that contain at least two strings from a set of strings. So if I have a set of strings {"A", "B" and ...
1
vote
2answers
90 views

Decomposing the search problem into several small problems

I am looking for papers/methods (or at least problem examples) where the original search problem $P$ can be solved by either: Searching through the original graph. or By decomposing it into several ...
0
votes
0answers
40 views

Search problems that can also be solved by junction trees and searching cliques

Assume having a graph $G_{variables}=(V,U)$ where $V=\{v_1,v_2,…,v_n\}$ is a set of variables; each variable $v_i\in V$ is associated with a set of possible values (it's domain) $dom(v_i)$. Let $P$ ...
2
votes
2answers
2k views

Artificial Intelligence: Condition for BFS being optimal

It is said in the book Artificial Intelligence: A Modern Approach for finding a solution on a tree using BFS that: breadth-first search is optimal if the path cost is a nondecreasing function of ...
1
vote
0answers
206 views

Does FNP-complete = NP-complete?

I can't seem to find this stated explicitly anywhere, which makes me wonder if I have it all wrong. So first, let's say we view problems in NP as degenerate problems in FNP, where the codomain of the ...
0
votes
2answers
811 views

Worst case scenario in binary search tree retrieval

Well, i have a binary search tree $T$ that is equilibrated by height witch has $2^d+c$ nodes ($c<2^d$). What is the number of comparisons that will occur in the worst case scenario, if we ask ...
1
vote
1answer
162 views

Efficient algorithms for finding a region in $\mathbf R^2$

This question is an extension of a previous question I've asked. Consider the rectangle $a<x<b , c<y<d$ in the $\mathbf R^2$ plane. Each point in this rectangle can be of kind #1 or #2 ...