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 ...
- 82.2k
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), (...
- 2,511
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 ...
- 143
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.♦
- 166k
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 ...
- 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 ...
- 3,473
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 ...
- 589
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 ...
- 31.6k
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 ...
- 279k
4
votes
Accepted
Minimum number of oracle call to solve Simon problem by a (NDTM) non-deterministic Turing machine?
No, your argument is not correct. A possible value of $s$ is $0^n$ (indeed, the decision version of Simon's problem is to distinguish $s=0^n$ from $s\ne0^n$, hence thus value is important).
Thus, your ...
- 2,221
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 ...
- 1,171
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 ...
- 13.9k
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 ...
- 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 ...
- 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.
- 22.8k
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 ...
- 5,509
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 ...
- 279k
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.♦
- 166k
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 ...
- 2,195
3
votes
Accepted
Finding a word that minimizes the sum of squared Hamming distances in a data set of words
If the Fréchet mean word can be any word, the problem is an instance of the $p$-Norm Hamming Centroid problem where $p=2$. Given a set of $m$ strings each of length $n$ and a real $k$, Chen et al., ...
- 1,041
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 ...
- 279k
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.♦
- 166k
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 $(...
- 955
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.♦
- 166k
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.♦
- 166k
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 ...
- 13.9k
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 ...
- 143
Only top scored, non community-wiki answers of a minimum length are eligible