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.
156 questions
1
vote
1
answer
51
views
What's an example of a problem that is in Psearch, but not in NPsearch?
I was told during a lecture that there exist computational problems that are within $\text{P}_\text{search}$ but are not in $\text{NP}_\text{search}$ this seems impossible to me because I feel like a ...
- 11
0
votes
1
answer
94
views
Definition of search-NP and search-P
Recall that a language $A$ is in NP iff it is of the form $$A = \{x \in \Sigma^* : (\exists w\in\Sigma^*)\ (x, w) \in R_A\},$$ for some relation $R_A$ such that membership of $(x, w)\in R_A$ can be ...
- 109
2
votes
1
answer
138
views
How to find a bijection $\Phi$ that maximizes the number of iterative replacements in a local rewriting system on $\left\{ 0, 1, 2, 3 \right\}$?
Problem. We study a local rewriting map defined on $5$-letter words over the alphabet $\{0,1,2,3\}$. A fixed forbidden-block set $\mathcal{F}$ of $16$ length-$3$ patterns is given by
$$\mathcal{F}= \{...
- 111
1
vote
1
answer
110
views
Are there other types of computational problems, and specialized tools/solvers for them?
The common types of computational problems that I can find seems to be the following: decision problems, search problems, counting problems, optimization problems, and function problems.
For decision ...
- 17
3
votes
1
answer
170
views
Finding a word that minimizes the sum of squared Hamming distances in a data set of words
Suppose we have a set of words of common length randomly sampled from a dictionary of words; assume you have access to that dictionary. Let $d(x,y)$ be the Hamming distance between words $x$ and $y$. ...
- 143
2
votes
2
answers
131
views
In class P, does decidability implies searchability?
I'm studying a course on Intro to Computability, and I couldn't find an answer.
Often, we refer to problems in $\text{P}$ as problems that we can "efficiently search a solution for" (where ...
- 21
3
votes
1
answer
398
views
Minimum number of oracle call to solve Simon problem by a (NDTM) non-deterministic Turing machine?
Simon's problem is a computational problem used to demonstrate an oracle separation between BQP and BPP classes.
It is known that the minimum number of oracle calls to be made by the BQP machine is $\...
- 229
0
votes
1
answer
80
views
Concise definitions for different types of computational problems
It is very common to define a decision problem $L$ in the following way. Let $f \colon \Sigma^{*} \to \{0,1\}$. Then $L = \{x \in \Sigma^* \mid f(x) = 1\}$. Effectively, $L$ contains all instances $x \...
- 13
0
votes
6
answers
404
views
Efficient data structure for multidimensional lookup
I'm doing a search problem over 18-tuples of non-negative integers. Some tuples are GOOD and some tuples are BAD, and I'm trying to list all of the GOOD tuples exactly once.
It turns out that if a ...
- 873
0
votes
0
answers
72
views
What algorithm should be used to find the closest set of dates?
I have tried to outline my problem as structured as possible, here is a rough overview, I am trying to find the best matching stay for a hotel booking system. If someone inputs check in and checkout ...
- 101
2
votes
1
answer
230
views
Maximum of a tritonic array
I have found out how to find the maximum of a "bitonic" array. The problem is as follows.
An array is bitonic if it is comprised of an increasing or decreasing sequence of integers followed ...
- 121
-1
votes
1
answer
139
views
How to get the TSP using DP algorithm can use 40 vertices?
I`m currently doing my homework that solving TSP using DP algorithm or branch and bound algorithm or backtracking algorithm only to solve up to 40 vertices and I can solve up to 30 vertices when I try ...
- 1
0
votes
0
answers
113
views
Graph Search Algorithms that are practically fast on dense graphs
I'm trying to do some research on graph search algorithms that are practically fast on relatively dense graphs. Besides the common ones like A* or Dijkstra's, what are some graph search algorithms ...
0
votes
2
answers
322
views
Time complexity to convert a truth table to a boolean circuit
The SAT problem is often explained in terms of truth tables. Given some random boolean circuit, calculate its truth table; does there exist an output of $1$ in the truth table?
But how about going the ...
- 263
2
votes
1
answer
157
views
Finding the smallest subset s.t. all elements satisfy condition, using as few tests as possible
I'm having a hard time describing this problem without an example, so let's go with this: Say you have a program that is made up of many files. There are some files you could delete, and, while it ...
- 23